{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #岛屿的最大面积"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxAreaOfIsland"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #岛屿的最大面积"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个由&nbsp;<code>0</code> 和 <code>1</code> 组成的非空二维数组&nbsp;<code>grid</code>&nbsp;，用来表示海洋岛屿地图。</p>\n",
    "\n",
    "<p>一个&nbsp;<strong>岛屿</strong>&nbsp;是由一些相邻的&nbsp;<code>1</code>&nbsp;(代表土地) 构成的组合，这里的「相邻」要求两个 <code>1</code> 必须在水平或者竖直方向上相邻。你可以假设&nbsp;<code>grid</code> 的四个边缘都被 <code>0</code>（代表水）包围着。</p>\n",
    "\n",
    "<p>找到给定的二维数组中最大的岛屿面积。如果没有岛屿，则返回面积为 <code>0</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://pic.leetcode-cn.com/1626667010-nSGPXz-image.png\" style=\"width: 452px; \" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]\n",
    "<strong>输出: </strong>6\n",
    "<strong>解释: </strong>对于上面这个给定矩阵应返回&nbsp;<code>6</code>。注意答案不应该是 <code>11</code> ，因为岛屿只能包含水平或垂直的四个方向的 <code>1</code> 。</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>grid = [[0,0,0,0,0,0,0,0]]\n",
    "<strong>输出: </strong>0</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 50</code></li>\n",
    "\t<li><code>grid[i][j] is either 0 or 1</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>注意：本题与主站 695&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/max-area-of-island/\">https://leetcode-cn.com/problems/max-area-of-island/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [ZL6zAn](https://leetcode.cn/problems/ZL6zAn/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [ZL6zAn](https://leetcode.cn/problems/ZL6zAn/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        X = len(grid)\n",
    "        Y = len(grid[0]) if X > 0 else 0\n",
    "        dx = [-1, 0, 1, 0]\n",
    "        dy = [0, -1, 0, 1]\n",
    "        def f1(x, y):\n",
    "            result = 0\n",
    "            if grid[x][y] == 1:\n",
    "                grid[x][y] = 0\n",
    "                result += 1\n",
    "                for i in range(4):\n",
    "                    nx = x + dx[i]\n",
    "                    ny = y + dy[i]\n",
    "                    if 0 <= nx and nx < X and 0 <= ny and ny < Y:\n",
    "                        result += f1(nx, ny)\n",
    "            return result\n",
    "        result = 0\n",
    "        for x in range(X):\n",
    "            for y in range(Y):\n",
    "                if grid[x][y] == 1:\n",
    "                    result = max(result, f1(x, y))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        a=[]\n",
    "        b=[]\n",
    "        \n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j]==1:\n",
    "                    a=[]\n",
    "                    a.append([i,j])\n",
    "                    grid[i][j]=-1\n",
    "                    d=1\n",
    "                    while True:\n",
    "                        c=[]\n",
    "                        for k in a:\n",
    "                            for m,n in [[-1,0],[1,0],[0,-1],[0,1]]:\n",
    "                                if k[0]+m>-1 and k[1]+n>-1:\n",
    "                                    try:\n",
    "                                        if grid[k[0]+m][k[1]+n]==1:\n",
    "                                            grid[k[0]+m][k[1]+n]=-1\n",
    "                                            d+=1\n",
    "                                            c.append([k[0]+m,k[1]+n])\n",
    "                                    except IndexError:\n",
    "                                        pass\n",
    "                        if len(c)==0:\n",
    "                            break\n",
    "                        a=c\n",
    "                    b.append(d)\n",
    "                    \n",
    "        if len(b)==0:\n",
    "            return 0\n",
    "        if len(b)==1:\n",
    "            return b[0]\n",
    "        return max(b)\n",
    "                        \n",
    "                        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    class UnionFindSet(object):\n",
    "        def __init__(self, data_list):\n",
    "            \"\"\"初始化两个字典，一个保存节点的父节点，另外一个保存父节点的大小\n",
    "            初始化的时候，将节点的父节点设为自身，size设为1\"\"\"\n",
    "            self.father_dict = {}\n",
    "            self.size_dict = {}\n",
    "\n",
    "            for node in data_list:\n",
    "                self.father_dict[node] = node\n",
    "                self.size_dict[node] = 1\n",
    "\n",
    "        def find_head(self, node):\n",
    "            \"\"\"使用递归的方式来查找父节点\n",
    "\n",
    "            在查找父节点的时候，顺便把当前节点移动到父节点上面\n",
    "            这个操作算是一个优化\n",
    "            \"\"\"\n",
    "            father = self.father_dict[node]\n",
    "            if(node != father):\n",
    "                father = self.find_head(father)\n",
    "            self.father_dict[node] = father\n",
    "            return father\n",
    "\n",
    "        def is_same_set(self, node_a, node_b):\n",
    "            \"\"\"查看两个节点是不是在一个集合里面\"\"\"\n",
    "            return self.find_head(node_a) == self.find_head(node_b)\n",
    "\n",
    "        def union(self, node_a, node_b):\n",
    "            \"\"\"将两个集合合并在一起\"\"\"\n",
    "            #print ('unioned')\n",
    "            if node_a is None or node_b is None:\n",
    "                return\n",
    "\n",
    "            a_head = self.find_head(node_a)\n",
    "            b_head = self.find_head(node_b)\n",
    "\n",
    "            if(a_head != b_head):\n",
    "                a_set_size = self.size_dict[a_head]\n",
    "                b_set_size = self.size_dict[b_head]\n",
    "                if(a_set_size >= b_set_size):\n",
    "                    self.father_dict[b_head] = a_head\n",
    "                    self.size_dict[a_head] = a_set_size + b_set_size\n",
    "                else:\n",
    "                    self.father_dict[a_head] = b_head\n",
    "                    self.size_dict[b_head] = a_set_size + b_set_size\n",
    "        def MaxNodeSize(self):\n",
    "            return max(list(self.size_dict.values()))\n",
    "    \n",
    "    def get_address(self,i,j,grid):\n",
    "        return i*len(grid[0])+j+1\n",
    "    def get_index(self,address,grid):\n",
    "        if address%len(grid[0])!=0:\n",
    "            return [int(address/len(grid[0])),(address%len(grid[0]))-1]\n",
    "        else:\n",
    "            return [int(address/len(grid[0]))-1,len(grid[0])-1]\n",
    "    def maxAreaOfIsland(self, grid):\n",
    "        dirts=[]\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j]==1:\n",
    "                    dirts.append(self.get_address(i,j,grid))\n",
    "        if dirts==[]:\n",
    "            return 0\n",
    "        Union=self.UnionFindSet(dirts)\n",
    "        for dirt in dirts:\n",
    "            i = self.get_index(dirt,grid)[0]\n",
    "            j=self.get_index(dirt,grid)[1]\n",
    "            if i!=len(grid)-1 and self.get_address(i+1,j,grid) in dirts: \n",
    "                if not Union.is_same_set(self.get_address(i,j,grid),self.get_address(i+1,j,grid)):\n",
    "                    Union.union(self.get_address(i,j,grid),self.get_address(i+1,j,grid))\n",
    "            if i!=0 and self.get_address(i-1,j,grid) in dirts: \n",
    "                if not Union.is_same_set(self.get_address(i,j,grid),self.get_address(i-1,j,grid)):\n",
    "                    Union.union(self.get_address(i,j,grid),self.get_address(i-1,j,grid))\n",
    "            if j!=len(grid[0])-1 and self.get_address(i,j+1,grid) in dirts: \n",
    "                if not Union.is_same_set(self.get_address(i,j,grid),self.get_address(i,j+1,grid)):\n",
    "                    Union.union(self.get_address(i,j,grid),self.get_address(i,j+1,grid))\n",
    "            if j!=0 and self.get_address(i,j-1,grid) in dirts: \n",
    "                if not Union.is_same_set(self.get_address(i,j,grid),self.get_address(i,j-1,grid)):\n",
    "                    Union.union(self.get_address(i,j,grid),self.get_address(i,j-1,grid))\n",
    "            #print(dirt)\n",
    "            #print([i,j])\n",
    "            #print(list(Union.father_dict.values()))\n",
    "        \n",
    "        return Union.MaxNodeSize()\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        maxArea = 0\n",
    "        row = len(grid)\n",
    "        column = len(grid[0])\n",
    "        totalPoints = [[0 for i in range(column)] for i in range(row)]\n",
    "        for i in range(0, row):\n",
    "            for j in range(0, column):\n",
    "                if grid[i][j] == 0:\n",
    "                    continue\n",
    "                else:\n",
    "                    if totalPoints[i][j]:\n",
    "                        continue\n",
    "                    totalPoints[i][j] = 1\n",
    "                    points = [[i, j]]\n",
    "                    newArea = []\n",
    "                    oldNum = 0\n",
    "                    while True:\n",
    "                        currNum = len(points)\n",
    "                        for p in range(oldNum, currNum):\n",
    "                            point = points[p]\n",
    "                            x = point[0]\n",
    "                            y = point[1]\n",
    "                            if x >= 1 and grid[x - 1][y] == 1 and totalPoints[x - 1][y] == 0:\n",
    "                                newArea.append([x - 1, y])\n",
    "                                totalPoints[x-1][y] = 1\n",
    "                            if y >= 1 and grid[x][y - 1] == 1 and totalPoints[x][y - 1] == 0:\n",
    "                                newArea.append([x, y - 1])\n",
    "                                totalPoints[x][y-1] =1\n",
    "                            if x < row - 1 and grid[x + 1][y] == 1 and totalPoints[x + 1][y] == 0:\n",
    "                                newArea.append([x + 1, y])\n",
    "                                totalPoints[x+1][y] = 1\n",
    "                            if y < column - 1 and grid[x][y + 1] == 1 and totalPoints[x][y + 1] == 0:\n",
    "                                newArea.append([x, y + 1])\n",
    "                                totalPoints[x][y+1] = 1\n",
    "                        if len(newArea) == 0:\n",
    "                            break\n",
    "                        else:\n",
    "                            oldNum = len(points)\n",
    "                            points = points + newArea\n",
    "                            newArea.clear()\n",
    "\n",
    "                    if len(points) > maxArea:\n",
    "                        maxArea = len(points)\n",
    "\n",
    "\n",
    "        return maxArea\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        tmp = []\n",
    "        for i in range(len(grid)):\n",
    "            tmp.append([])\n",
    "            for j in range(len(grid[0])):\n",
    "                tmp[i].append(False)\n",
    "        max_area = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if tmp[i][j]:\n",
    "                    continue\n",
    "                if grid[i][j] == 0:\n",
    "                    tmp[i][j] = True\n",
    "                    continue\n",
    "                stack = [[i, j]]\n",
    "                current_area = 0\n",
    "                while stack:\n",
    "                    row, column = stack.pop()\n",
    "                    if row < 0 or column < 0 or row >= len(grid) or column >= len(grid[0]):\n",
    "                        continue\n",
    "                    if tmp[row][column]:\n",
    "                        continue\n",
    "                    tmp[row][column] = True\n",
    "                    if grid[row][column] == 0:\n",
    "                        continue\n",
    "                    current_area += 1\n",
    "                    stack.append([row + 1, column])\n",
    "                    stack.append([row - 1, column])\n",
    "                    stack.append([row, column + 1])\n",
    "                    stack.append([row, column - 1])\n",
    "                max_area = max(max_area, current_area)\n",
    "        return max_area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        maxnum=0\n",
    "        h=len(grid)\n",
    "        for i in range(h):\n",
    "            m=len(grid[i])\n",
    "            for j in range(m):\n",
    "                if grid[i][j]==1:\n",
    "                    num=0\n",
    "                    a=[(i,j)]\n",
    "                    grid[i][j]=0\n",
    "                    while len(a)>0:\n",
    "                        num+=1\n",
    "                        # print(num,a[-1],a)\n",
    "                        ti,tj=a[-1][0],a[-1][1]\n",
    "                        a.pop()\n",
    "                        # 查找这个位置有没有连起来\n",
    "                        if ti>0 and grid[ti-1][tj]==1:#left\n",
    "                            grid[ti-1][tj]=0\n",
    "                            a.append((ti-1,tj))\n",
    "                        if ti<h-1 and grid[ti+1][tj]==1:#right\n",
    "                            grid[ti+1][tj]=0\n",
    "                            a.append((ti+1,tj))\n",
    "                        if tj>0 and grid[ti][tj-1]==1:#up\n",
    "                            grid[ti][tj-1]=0\n",
    "                            a.append((ti,tj-1))\n",
    "                        if tj<m-1 and grid[ti][tj+1]==1:#down\n",
    "                            grid[ti][tj+1]=0\n",
    "                            a.append((ti,tj+1))    \n",
    "                    if num>maxnum:maxnum=num\n",
    "        return maxnum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if(grid[i][j]!=-1):\n",
    "                    if grid[i][j]==1:\n",
    "                        ans = max(self.dfs(i,j,grid),ans)\n",
    "                    else:\n",
    "                        grid[i][j]==-1\n",
    "        return ans\n",
    "                         \n",
    "    def dfs(self,r,c,grid):\n",
    "        cnt = 1\n",
    "        direction = [[1,0],[0,1],[-1,0],[0,-1]]\n",
    "        q = collections.deque()\n",
    "        grid[r][c] = -1\n",
    "        q.append((r,c))\n",
    "        while(q):\n",
    "            curr = q.popleft()\n",
    "            for i in range(4):\n",
    "                tmp = (curr[0]+direction[i][0],curr[1]+direction[i][1])\n",
    "                if 0<=tmp[0]<len(grid) and 0<=tmp[1]<len(grid[0]) and grid[tmp[0]][tmp[1]]==1:\n",
    "                    grid[tmp[0]][tmp[1]] = -1\n",
    "                    q.append(tmp)\n",
    "                    cnt+=1\n",
    "        return cnt\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        rows=len(grid)\n",
    "        if rows==0:\n",
    "            return 0\n",
    "        cols=len(grid[0])\n",
    "        if cols==0:\n",
    "            return 0\n",
    "        max_area=0\n",
    "        for idx in range(rows):\n",
    "            for idy in range(cols):\n",
    "                if grid[idx][idy]==0:\n",
    "                    continue\n",
    "                area=0\n",
    "                stack=[(idx,idy)]\n",
    "                while len(stack)>0:\n",
    "                    x,y=stack.pop()\n",
    "                    if 0<=x<rows and 0<=y<cols and grid[x][y]==1:\n",
    "                        grid[x][y]=0\n",
    "                        area+=1\n",
    "                        stack.extend([(x-1,y),(x+1,y),(x,y-1),(x,y+1)])\n",
    "                max_area=max(area,max_area)\n",
    "        return max_area\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        res = 0\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                res = max(res, self.dfs(i, j, m, n, grid))\n",
    "        return res\n",
    "\n",
    "    def dfs(self, i, j, m, n, grid):\n",
    "        if i < 0 or i >=m or j < 0 or j >= n:\n",
    "            return 0\n",
    "        if grid[i][j] == 1:\n",
    "            grid[i][j] = 2\n",
    "            res = 1\n",
    "            res += self.dfs(i+1, j, m, n,grid)\n",
    "            res += self.dfs(i-1, j, m, n, grid)\n",
    "            res += self.dfs(i, j+1, m, n, grid)\n",
    "            res += self.dfs(i, j-1, m, n, grid)\n",
    "            return res\n",
    "        else:\n",
    "            return 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        maximum = 0\n",
    "        for i in range(0,len(grid)):\n",
    "            for j in range(0,len(grid[0])):\n",
    "                if grid[i][j] == 1:\n",
    "                    temp = self.countArea(grid, i, j)\n",
    "                    if temp > maximum:\n",
    "                        maximum = temp\n",
    "        return maximum\n",
    "    \n",
    "    def countArea(self, grid, i, j):\n",
    "        grid[i][j] = 0\n",
    "        res = 1\n",
    "        if i-1 >= 0 and grid[i-1][j] == 1:\n",
    "            res += self.countArea(grid, i-1, j)\n",
    "        if i+1 < len(grid) and grid[i+1][j] == 1:\n",
    "            res += self.countArea(grid, i+1, j)\n",
    "        if j-1 >= 0 and grid[i][j-1] == 1:\n",
    "            res += self.countArea(grid, i, j-1)\n",
    "        if j+1 < len(grid[0]) and grid[i][j+1] == 1:\n",
    "            res += self.countArea(grid, i ,j+1)\n",
    "        \n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(grid) == 0:\n",
    "            return 0\n",
    "        \n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        \n",
    "        max_Area = 0\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    max_Area = max(max_Area, self.dfs(grid, i, j))\n",
    "        return max_Area\n",
    "    \n",
    "    def dfs(self, grid, i, j):\n",
    "        if i<0 or i>=len(grid) or j<0 or j>=len(grid[0]) or grid[i][j] == 0:\n",
    "            return 0\n",
    "        grid[i][j] = 0\n",
    "        res = 1 + self.dfs(grid, i-1, j) + self.dfs(grid, i+1, j) + self.dfs(grid, i, j-1) + self.dfs(grid, i, j+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: 'List[List[int]]') -> 'int':\n",
    "        if not grid:\n",
    "            return 0\n",
    "        dires = [[1,0], [0,1], [-1,0], [0,-1]]\n",
    "        ans = [0]\n",
    "        tmp = (len(grid), len(grid[0]))\n",
    "        step = [0]\n",
    "        def dfs(row, col):\n",
    "            if row >= tmp[0] or col >= tmp[1] or row < 0 or col < 0:\n",
    "                ans[0] = max(step[0], ans[0])\n",
    "                return\n",
    "            if grid[row][col] == 0 or grid[row][col] == -1:\n",
    "                ans[0] = max(step[0], ans[0])\n",
    "                return \n",
    "            \n",
    "            grid[row][col] = -1\n",
    "            step[0] += 1\n",
    "            for dire in dires:\n",
    "                nextr = row + dire[0]\n",
    "                nextc = col + dire[1]\n",
    "                dfs(nextr, nextc)\n",
    "                \n",
    "        for row in range(tmp[0]):\n",
    "            for col in range(tmp[1]):\n",
    "                if grid[row][col] not in {0, -1}:\n",
    "                    dfs(row, col)\n",
    "                    #print(grid)\n",
    "                    step[0] = 0\n",
    "        return ans[0]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        def find(i,j):\n",
    "            if i<0 or i>=r or j <0 or j>=c:return 0\n",
    "            \n",
    "            if grid[i][j]:\n",
    "                grid[i][j]=0\n",
    "                \n",
    "                return 1+find(i-1,j)+find(i+1,j)+find(i,j-1)+find(i,j+1)\n",
    "                 \n",
    "            else:return 0\n",
    "                \n",
    "                \n",
    "        res=[]\n",
    "        r,c=len(grid),len(grid[0])\n",
    "        \n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                res.append(find(i,j))\n",
    "        return max(res) if res else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not grid or not grid[0]:\n",
    "            return 0\n",
    "\n",
    "        m, n = len(grid), len(grid[0])      \n",
    "        visited = [[0] * n for i in range(m)]\n",
    "        directions = ((1, 0), (-1, 0), (0, 1), (0, -1))\n",
    "\n",
    "        def dfs(pos):\n",
    "            i, j = pos\n",
    "            if not visited[i][j]:\n",
    "                visited[i][j] = 1\n",
    "                length[0] += 1\n",
    "                for x, y in directions:\n",
    "                    ii, jj = i + x, j + y\n",
    "                    if 0 <= ii < m and 0 <= jj < n:\n",
    "                        if grid[ii][jj] == grid[i][j]:\n",
    "                            dfs((ii, jj))\n",
    "\n",
    "        record = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if not visited[i][j] and grid[i][j] == 1:\n",
    "                    length = [0]\n",
    "                    dfs((i, j))\n",
    "                    record = max(record, length[0])\n",
    "\n",
    "        return record"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        def cal(L,i,j):\n",
    "            c = 1\n",
    "            x = len(L)\n",
    "            y = len(L[0])\n",
    "            L[i][j] = 0\n",
    "            if i-1>=0 and L[i-1][j]: #上\n",
    "                c = c + cal(L,i-1,j)\n",
    "            if j+1 < y and L[i][j+1]: #右\n",
    "                c = c + cal(L,i,j+1)\n",
    "            if  i+1 < x and L[i+1][j]: #下\n",
    "                c = c + cal(L,i+1,j)\n",
    "            if j-1>=0 and L[i][j-1]: #左\n",
    "                c = c + cal(L,i,j-1)\n",
    "            return c\n",
    "\n",
    "\n",
    "        lenr = len(grid)\n",
    "        lenc = len(grid[0])\n",
    "        count = 0\n",
    "        result = 0\n",
    "        for i in range(lenr):\n",
    "            for j in range(lenc):\n",
    "                if grid[i][j] == 1:\n",
    "                    count = cal(grid,i,j)\n",
    "                    result = max(result,count)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        max_area = 0\n",
    "        if len(grid) == 0:\n",
    "            return max_area\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 1:\n",
    "                    max_area = max(max_area, self.dfs(i, j, grid))\n",
    "        return max_area\n",
    "    \n",
    "    def dfs(self, i, j, grid):\n",
    "        area = 0\n",
    "        if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]):\n",
    "            return area\n",
    "        if grid[i][j] == 1:\n",
    "            area += 1\n",
    "            grid[i][j] = 0\n",
    "            direction = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "            for d in direction:\n",
    "                area += self.dfs(i + d[0], j + d[1], grid)\n",
    "        return area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        if len(grid)==0 or len(grid[0])==0:\n",
    "            return 0\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        maxarea=0\n",
    "        \n",
    "        def dfs(grid, i, j, m, n):\n",
    "            if i<0 or i>=m or j<0 or j>=n or grid[i][j]==0:\n",
    "                return 0\n",
    "            grid[i][j]=0\n",
    "            return 1+dfs(grid, i+1, j, m, n)+dfs(grid, i-1, j, m, n)+dfs(grid, i, j+1, m, n)+dfs(grid, i, j-1, m, n)\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    maxarea = max(dfs(grid, i, j, m, n), maxarea)\n",
    "        return maxarea"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid):\n",
    "        f = dict()\n",
    "        _max = 0\n",
    "        for floor in grid:\n",
    "            s = dict()\n",
    "            for i in range(len(floor)):\n",
    "                if floor[i] == 1:\n",
    "                    # 有水平连接\n",
    "                    head = self.get_head(i, s)\n",
    "                    if head == i:\n",
    "                        s[i] = 1\n",
    "                    else:\n",
    "                        s[head] += 1\n",
    "                        s[i] = str(head)\n",
    "\n",
    "                    f_head = self.get_head(i+1, f)\n",
    "                    # 垂直相连时\n",
    "                    if f_head != i+1:\n",
    "                        # 水平父节点\n",
    "                        tem = i\n",
    "                        if type(s[i]) == str:\n",
    "                            tem = int(s[i])\n",
    "\n",
    "                        fn = f[f_head]\n",
    "                        # 上层岛屿已和这层岛屿连接\n",
    "                        if type(fn) == tuple:\n",
    "                            # 上层岛屿和这层岛屿连接的头点\n",
    "                            head = fn[0]\n",
    "                            # 判断水平父岛屿和垂直父岛屿是否是同一个，是同一个则不用加\n",
    "                            if head != tem:\n",
    "                                s[head] += s[tem]\n",
    "                                s[tem] = str(head)\n",
    "                            # tem = fn[0]\n",
    "                            # s[i] = str(tem)\n",
    "                            # if flag:s\n",
    "                            #     fn = 0\n",
    "                            # else:\n",
    "                            #     fn = 0 if i-1 >= 0 and floor[i-1] == 1 else 1\n",
    "                        # 未和这层连接\n",
    "                        else:\n",
    "                            f[f_head] = (tem, )\n",
    "                            s[tem] += fn\n",
    "\n",
    "            for v in f.values():\n",
    "                if type(v) == int and v > _max:\n",
    "                    _max = v\n",
    "            f = s\n",
    "\n",
    "        # 最后来一次\n",
    "        for v in f.values():\n",
    "            if type(v) == int and v > _max:\n",
    "                _max = v\n",
    "        return _max\n",
    "\n",
    "    def get_head(self, i, s):\n",
    "        if type(s.get(i-1)) == int:\n",
    "            return i-1\n",
    "        elif type(s.get(i-1)) == str:\n",
    "            return self.get_head(int(s[i-1])+1, s)\n",
    "        elif type(s.get(i-1)) == tuple:\n",
    "            return i-1\n",
    "        else:\n",
    "            return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        if not grid:\n",
    "            return 0\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        visited=[[False]*n for _ in range(0,m)]\n",
    "        #print(visited)\n",
    "        level=0\n",
    "        res=[]\n",
    "        for i in range(0,m):\n",
    "            for j in range(0,n):\n",
    "                if grid[i][j]==1 and  visited[i][j]==False:\n",
    "                    queue=[(i,j)]\n",
    "                    visited[i][j]=True\n",
    "                    #print(i,j)\n",
    "                    res.append([])\n",
    "                    #print(res)\n",
    "                    while queue:\n",
    "                        x,y=queue.pop(0)\n",
    "                        res[level].append((x,y))\n",
    "                        for dx,dy in [[0,1],[0,-1],[-1,0],[1,0]]:\n",
    "                            newX=x+dx\n",
    "                            newY=y+dy\n",
    "                            if newX>=0 and newX<m and newY>=0 and newY<n and grid[newX][newY]==1 and visited[newX][newY]==False:\n",
    "                                visited[newX][newY]=True\n",
    "                                queue.append((newX,newY))\n",
    "                    level=level+1\n",
    "        print(res)\n",
    "        maxL=0\n",
    "        for l in res:\n",
    "            maxL=max(len(l),maxL)\n",
    "        return maxL\n",
    "                \n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        if not grid:\n",
    "            return 0\n",
    "\n",
    "        total0 = 0\n",
    "        total1 = 0\n",
    "        r = len(grid)\n",
    "        c = len(grid[0])\n",
    "        for i in range(len(grid)):\n",
    "            total0 += grid[i].count(0)\n",
    "        if total0 == r*c: \n",
    "            return 0\n",
    "        \n",
    "        visited = [[False for i in range(c)] for j in range(r)]\n",
    "        queue = []\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                if grid[i][j] == 1 and not visited[i][j]: #if it is a island and not visit yet\n",
    "                    temp = 1\n",
    "                    visited[i][j] = True\n",
    "                    queue.append([i,j])\n",
    "                    while queue:\n",
    "                        x,y = queue.pop(0)\n",
    "                        for row,col in [[x-1,y],[x+1,y],[x,y-1],[x,y+1]]:\n",
    "                            if 0<=row<r and 0<=col<c and not visited[row][col]:\n",
    "                                if grid[row][col] == 1:\n",
    "                                    temp += 1\n",
    "                                    queue.append([row,col])\n",
    "                                    visited[row][col] = True\n",
    "\n",
    "                    ans = max(ans,temp)\n",
    "                    temp = 0\n",
    "\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        l = []\n",
    "        res = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 0:\n",
    "                    continue\n",
    "                else:\n",
    "                    l.append([i,j])\n",
    "                    grid[i][j] = 0\n",
    "                    dao = 0\n",
    "                    while l:\n",
    "                        dao +=1\n",
    "                        res = max(res,dao)\n",
    "\n",
    "                        #print(l,dao)\n",
    "\n",
    "                        i,j = l.pop(0)\n",
    "                        for x,y in [[-1,0],[0,-1],[1,0],[0,1]]:\n",
    "                            xx = x+i\n",
    "                            yy = y+j\n",
    "                            if 0 <= xx <len(grid) and 0 <= yy < len(grid[0]) and grid[xx][yy]>0:\n",
    "                                l.append([xx,yy])\n",
    "                                grid[xx][yy] = 0\n",
    "\n",
    "\n",
    "                        \n",
    "\n",
    "        return res\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        if not grid or len(grid[0])<1:\n",
    "            return 0\n",
    "        \n",
    "        rows, cols = len(grid), len(grid[0])\n",
    "        max_area = 0\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                if grid[i][j] == 1:\n",
    "                    max_area = max(max_area, self.bfs(grid, i, j, rows, cols))\n",
    "        return max_area\n",
    "    \n",
    "    def bfs(self, grid, x, y, rows, cols):\n",
    "        steps = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "        queue = [(x, y)]\n",
    "        area = 1\n",
    "        grid[x][y] = 0\n",
    "        while queue:\n",
    "            x, y = queue.pop(0)\n",
    "            for step in steps:\n",
    "                x_, y_ = x+step[0], y+step[1]\n",
    "                if 0<=x_<rows and 0<=y_<cols and grid[x_][y_]==1:\n",
    "                    area += 1\n",
    "                    queue.append((x_, y_))\n",
    "                    grid[x_][y_] = 0\n",
    "        return area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        dx=[-1,0,0,1]\n",
    "        dy=[0,1,-1,0]\n",
    "        maxs=0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                s=0\n",
    "                if grid[i][j]==1:\n",
    "                    grid[i][j]=0\n",
    "                    s+=1\n",
    "                    #island=[]\n",
    "                    #island.append([i,j])\n",
    "                    island=collections.deque()\n",
    "                    island.append([i,j])\n",
    "                    while len(island)>0:\n",
    "                        #x,y=island[0]\n",
    "                        #del island[0]\n",
    "                        x,y=island.popleft()\n",
    "                        for k in range(4):\n",
    "                            nx=x+dx[k]\n",
    "                            ny=y+dy[k]\n",
    "                            if 0<=nx<len(grid) and 0<=ny<len(grid[0]) and grid[nx][ny]==1 :\n",
    "                                grid[nx][ny]=0\n",
    "                                s+=1\n",
    "                                island.append([nx,ny])\n",
    "                    maxs=max(s,maxs)\n",
    "        return maxs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid) -> int:\n",
    "        if not grid or not grid[0]:\n",
    "            return 0\n",
    "\n",
    "        # 这一段是套路\n",
    "        rows, cols = len(grid), len(grid[0])  # rows cols\n",
    "        marked = [[False for i in range(cols)] for j in range(rows)]  # 是否走过\n",
    "        directions = [[-1, 0], [0, 1], [1, 0], [0, -1]]  # 上右下左\n",
    "        queue = []\n",
    "\n",
    "        max_area = 0\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                if marked[i][j] is False and grid[i][j] == 1:\n",
    "                    queue.append([i, j])  # 入队\n",
    "                    marked[i][j] = True   # 标记\n",
    "                    current_area = 0\n",
    "                    while queue:\n",
    "                        current = queue.pop(0)\n",
    "                        current_area += 1\n",
    "                        for direction in directions:\n",
    "                            next_x = current[0] + direction[0]\n",
    "                            next_y = current[1] + direction[1]\n",
    "                            if 0 <= next_x < rows and 0 <= next_y < cols and marked[next_x][next_y] is False and grid[next_x][next_y] == 1:\n",
    "                                queue.append([next_x, next_y])\n",
    "                                marked[next_x][next_y] = True\n",
    "                    max_area = max(max_area, current_area)\n",
    "        \n",
    "        return max_area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        if not grid: return 0\n",
    "        rownum = len(grid)\n",
    "        colnum = len(grid[0])\n",
    "        land = []\n",
    "        for i in range(rownum):\n",
    "            for j in range(colnum):\n",
    "                if grid[i][j]==1:\n",
    "                    land.append((i,j))\n",
    "        if not land: return 0\n",
    "        maxarea = 0\n",
    "        x = [1,0,0,-1]\n",
    "        y = [0,1,-1,0]\n",
    "        for a in land:\n",
    "            if grid[a[0]][a[1]]==0:\n",
    "                continue\n",
    "            stack = [a]\n",
    "            grid[a[0]][a[1]]=0\n",
    "            area = 1\n",
    "            while stack:\n",
    "                cur = stack.pop()\n",
    "                for b in range(4):\n",
    "                    if 0<=cur[0]+x[b]<rownum and 0<=cur[1]+y[b]<colnum and grid[cur[0]+x[b]][cur[1]+y[b]]==1:\n",
    "                        stack.append((cur[0]+x[b],cur[1]+y[b]))\n",
    "                        area += 1\n",
    "                        grid[cur[0]+x[b]][cur[1]+y[b]]=0\n",
    "            maxarea = max(maxarea,area)\n",
    "        return maxarea\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        leni = len(grid)\n",
    "        if leni == 0:\n",
    "            return 0\n",
    "        lenj = len(grid[0])\n",
    "        result = 0\n",
    "        #check = [[0] * lenj for _ in range(leni)]\n",
    "        for i in range(leni):\n",
    "            if sum(grid[i]) > 0:\n",
    "                for j in range(lenj):\n",
    "                    print(i)\n",
    "                    print(j)\n",
    "                    if grid[i][j] == 1:\n",
    "                        tqueue = queue.Queue()\n",
    "                        grid[i][j] = 0\n",
    "                        tqueue.put([i, j])\n",
    "                        tmp_s = 0\n",
    "                        while not tqueue.empty():\n",
    "                            f, s = tqueue.get()\n",
    "                            tmp_s += 1\n",
    "                            for x, y in [[f+1, s], [f-1, s], [f, s-1], [f, s+1]]:\n",
    "                                if 0 <= x < leni and 0 <= y < lenj:\n",
    "                                    if grid[x][y] == 1:\n",
    "                                        grid[x][y] = 0\n",
    "                                        tqueue.put([x, y])\n",
    "                        result = max(tmp_s, result)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        row=len(grid)\n",
    "        if not row:\n",
    "            return 0\n",
    "        col=len(grid[0])\n",
    "        if not col:\n",
    "            return 0\n",
    "        maxcnt=0\n",
    "        queue=[]\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j]==1:\n",
    "                    cnt=0\n",
    "                    queue.append((i,j))\n",
    "                    cnt+=1\n",
    "                    while queue:\n",
    "                        cur_i,cur_j=queue.pop(0)\n",
    "                        grid[cur_i][cur_j]=0\n",
    "                        for x,y in [(1,0),(-1,0),(0,1),(0,-1)]:\n",
    "                            tmp_i,tmp_j=cur_i+x,cur_j+y\n",
    "                            if 0<=tmp_i<row and 0<=tmp_j<col and grid[tmp_i][tmp_j]==1 and (tmp_i,tmp_j)not in queue:\n",
    "                                queue.append((tmp_i,tmp_j))\n",
    "                                cnt+=1\n",
    "                    maxcnt=max(maxcnt,cnt)\n",
    "        return maxcnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        maxArea = 0\n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                stack = deque()\n",
    "                stack.append((r, c))\n",
    "                area = 0\n",
    "\n",
    "                while stack:\n",
    "                    r_, c_ = stack.popleft()\n",
    "\n",
    "                    if r_ >= 0 and r_ < m and c_ >= 0 and c_ < n and grid[r_][c_] == 1:\n",
    "                        area += 1\n",
    "                        grid[r_][c_] = 2\n",
    "\n",
    "                        stack.append((r_ + 1, c_))\n",
    "                        stack.append((r_ - 1, c_))\n",
    "                        stack.append((r_, c_ + 1))\n",
    "                        stack.append((r_, c_ - 1))\n",
    "\n",
    "                if maxArea < area:\n",
    "                    maxArea = area\n",
    "        \n",
    "        return maxArea"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        def bfs(i,j):\n",
    "            queue = [(i,j)]\n",
    "            grid[i][j] = 0\n",
    "            area = 1\n",
    "            while queue:\n",
    "                x,y = queue.pop(0)\n",
    "                for new_x,new_y in [(x + 1,y),(x - 1,y),(x,y + 1),(x,y - 1)]:\n",
    "                    if 0 <= new_x < n and 0 <= new_y < m and grid[new_x][new_y] == 1:\n",
    "                        grid[new_x][new_y] = 0\n",
    "                        area += 1\n",
    "                        queue.append((new_x,new_y))\n",
    "            return area\n",
    "\n",
    "        n,m = len(grid),len(grid[0])\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 1:\n",
    "                    res = max(res,bfs(i,j))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        for i, l in enumerate(grid):\n",
    "            for j, n in enumerate(l):\n",
    "                cur = 0\n",
    "                q = collections.deque([(i, j)])\n",
    "                while q:\n",
    "                    cur_i, cur_j = q.popleft()\n",
    "                    if cur_i < 0 or cur_j < 0 or cur_i == len(grid) or cur_j == len(grid[0]) or grid[cur_i][cur_j] != 1:\n",
    "                        continue\n",
    "                    cur += 1\n",
    "                    grid[cur_i][cur_j] = 0\n",
    "                    for di, dj in [[0, 1], [0, -1], [1, 0], [-1, 0]]:\n",
    "                        next_i, next_j = cur_i + di, cur_j + dj\n",
    "                        q.append((next_i, next_j))\n",
    "                ans = max(ans, cur)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        H, W = len(grid), len(grid[0])\n",
    "\n",
    "        def get_area(i, j):\n",
    "            area = 0\n",
    "            queue = []\n",
    "            visited = set()\n",
    "\n",
    "            queue.append((i, j))\n",
    "            visited.add((i, j))\n",
    "            # grid[i][j] = 2\n",
    "            # area += 1\n",
    "            \n",
    "            while queue:\n",
    "                a, b = queue.pop(0)\n",
    "                grid[a][b] = 2\n",
    "                area += 1\n",
    "                for (a, b) in ((a+1, b), (a-1, b), (a, b+1), (a, b-1)):\n",
    "                    if not ((0<=a<=H-1) and (0<=b<=W-1)):\n",
    "                        continue\n",
    "                    if not grid[a][b] == 1:\n",
    "                        continue\n",
    "                    if (a, b) in visited:\n",
    "                        continue\n",
    "                    \n",
    "                    queue.append((a, b))\n",
    "                    visited.add((a, b))\n",
    "                    # grid[a][b] = 2\n",
    "                    # area += 1\n",
    "            \n",
    "            return area\n",
    "\n",
    "        \n",
    "        max_area = 0\n",
    "        for i in range(H):\n",
    "            for j in range(W):\n",
    "                if grid[i][j] == 1:\n",
    "                    area = get_area(i, j)\n",
    "                    max_area = max(area, max_area)\n",
    "        \n",
    "        return max_area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        directions = ((1, 0), (0, 1), (-1, 0), (0, -1))\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    area = 1\n",
    "                    grid[i][j] = 0\n",
    "                    queue = deque([[i, j]])\n",
    "                    while queue:\n",
    "                        [ti, tj] = queue.popleft()\n",
    "                        for (r, c) in directions:\n",
    "                            if 0 <= (ti + r) < m and 0 <= (tj + c) < n and grid[ti+r][tj+c] == 1:\n",
    "                                grid[ti+r][tj+c] = 0\n",
    "                                queue.append([ti+r, tj+c])\n",
    "                                area += 1\n",
    "                    ans = max(ans, area)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "        def bfs(x, y):\n",
    "            grid[x][y] = 0\n",
    "            \n",
    "            q = []\n",
    "            q.append([x, y])\n",
    "            area = 1\n",
    "\n",
    "            directions = [[-1,0],[1,0],[0,-1],[0,1]]\n",
    "            while len(q) != 0:\n",
    "                # [new_x, new_y] = q.pop(0)\n",
    "                element = q.pop(0)\n",
    "                for direction in directions:\n",
    "                    # new_x += direction[0]\n",
    "                    # new_y += direction[1]\n",
    "                    new_x = element[0] + direction[0]\n",
    "                    new_y = element[1] + direction[1]\n",
    "                    if 0<=new_x<m and 0<=new_y<n and grid[new_x][new_y] == 1:\n",
    "                        grid[new_x][new_y] = 0\n",
    "                        q.append([new_x, new_y])\n",
    "                        area += 1\n",
    "            return area\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    area = bfs(i, j)\n",
    "                    if area > ans:\n",
    "                        ans = area\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def DFS(self,grid: List[List[int]],checklist, i:int, j:int):\n",
    "        \n",
    "    #     checklist[i][j] = 1\n",
    "    #     self.area += 1\n",
    "    #     for nexti, nextj in [(i,j+1), (i,j-1), (i+1,j),(i-1,j)]:\n",
    "    #         if ((0 <= nexti < self.x and 0 <= nextj < self.y) and (grid[nexti][nextj] == 1) and checklist[nexti][nextj] == 0):\n",
    "    #             self.DFS(grid, checklist, nexti, nextj)\n",
    "\n",
    "    # def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "    #     #m为x，n为y\n",
    "    #     self.x = len(grid)\n",
    "    #     self.y = len(grid[0])\n",
    "    #     ans = 0\n",
    "    #     checklist = [[0] * self.y for _ in range(self.x)]\n",
    "\n",
    "    #     for i in range(self.x):\n",
    "    #         for j in range(self.y):\n",
    "    #             if (grid[i][j] == 1 and checklist[i][j] == 0):\n",
    "    #                 self.area = 0\n",
    "    #                 self.DFS(grid, checklist, i, j)\n",
    "    #                 ans = max(ans, self.area)\n",
    "\n",
    "    #     return ans\n",
    "\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        x_len, y_len = len(grid), len(grid[0])\n",
    "        ans = 0\n",
    "        \n",
    "        checklist = [[0] * y_len for _ in range(x_len)]\n",
    "\n",
    "        for i in range(x_len):\n",
    "            for j in range(y_len):\n",
    "                if grid[i][j] == 1 and checklist[i][j] == 0:\n",
    "                    q = deque([(i,j)])\n",
    "                    checklist[i][j] = 1\n",
    "                    curarea = 0\n",
    "                    while len(q) > 0:\n",
    "                        x,y = q.popleft()\n",
    "                        curarea += 1\n",
    "                        for xnext, ynext in [(x,y+1),(x,y-1),(x+1,y),(x-1,y)]:\n",
    "                            if ((0 <= xnext < x_len and 0 <= ynext < y_len) and grid[xnext][ynext] == 1 and checklist[xnext][ynext] == 0):\n",
    "                                q.append((xnext,ynext))\n",
    "                                checklist[xnext][ynext] = 1\n",
    "                    ans = max(ans, curarea)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        def island(grid,a,b,sur_max):\n",
    "            isl = []\n",
    "            isl.append((a,b))\n",
    "            grid[a][b] =0\n",
    "            sur = 1\n",
    "            while isl:\n",
    "                (i,j) = isl.pop()\n",
    "                for (p,q) in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:\n",
    "                    if 0<=p<m and 0<=q<n and grid[p][q] ==1:\n",
    "                        grid[p][q] = 0\n",
    "                        isl.append((p,q))\n",
    "                        sur +=1\n",
    "            return max(sur_max,sur)\n",
    "\n",
    "        sur_max = 0\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] ==1:\n",
    "                    sur_max = island(grid,i,j,sur_max)\n",
    "        return sur_max\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        if len(grid)==0 or len(grid[0]) == 0:\n",
    "            return 0\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        count = 0\n",
    "        visited = [[0 for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        def dfs(i, j, c, area):\n",
    "            for x, y in [(i+1,j), (i-1,j), (i,j+1), (i,j-1)]:\n",
    "                if x >= m or x < 0 or y >= n or y < 0:\n",
    "                    continue\n",
    "                if grid[x][y] == 0 or visited[x][y] != 0:\n",
    "                    continue\n",
    "                visited[x][y] = c\n",
    "                area+=1\n",
    "                area = dfs(x,y,c,area)\n",
    "\n",
    "            return area\n",
    "        \n",
    "        def bfs(i, j, c, area):\n",
    "            que = deque([(i,j)])\n",
    "            while que:\n",
    "                i, j = que.popleft()\n",
    "\n",
    "                for x, y in [(i+1,j), (i-1,j), (i,j+1), (i,j-1)]:\n",
    "                    if x >= m or x < 0 or y >= n or y < 0:\n",
    "                        continue\n",
    "                    if grid[x][y] == 0 or visited[x][y] != 0:\n",
    "                        continue\n",
    "                    visited[x][y] = c\n",
    "                    area+=1\n",
    "                    que.append((x,y))\n",
    "                    # area = dfs(x,y,c,area)\n",
    "\n",
    "            return area\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1 and visited[i][j] == 0:\n",
    "                    count += 1\n",
    "                    visited[i][j] = count\n",
    "                    area = bfs(i, j, count, 1)\n",
    "                    res = max(res, area)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        direction = [[-1,0],[1,0],[0,1],[0,-1]]\n",
    "        # def dfs(x,y):\n",
    "        #     if x < 0 or y < 0 or x >= len(grid) or y >= len(grid[0]):\n",
    "        #         return 0\n",
    "        #     if grid[x][y] == 0:\n",
    "        #         return 0\n",
    "        #     area = 1\n",
    "        #     grid[x][y] = 0\n",
    "        #     for p in direction:\n",
    "        #         area += dfs(x-p[0], y-p[1])\n",
    "        #     return area\n",
    "            \n",
    "        # max_area = 0\n",
    "        # for i in range(len(grid)):\n",
    "        #     for j in range(len(grid[0])):\n",
    "        #         if grid[i][j] == 0:\n",
    "        #             continue\n",
    "        #         max_area = max(max_area, dfs(i,j))\n",
    "        # return max_area\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        max_area = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    continue\n",
    "                queue = []\n",
    "                queue.append([i,j])\n",
    "                area = 0\n",
    "                while queue != []:\n",
    "                    point = queue[-1]\n",
    "                    queue = queue[:-1]\n",
    "                    x,y = point\n",
    "                    if x < 0 or y < 0 or x >= m or y >= n:\n",
    "                        continue\n",
    "                    if grid[x][y] == 0:\n",
    "                        continue\n",
    "                    area += 1\n",
    "                    grid[x][y] = 0\n",
    "                    for dx, dy in direction:\n",
    "                        queue.append([x+dx, y+dy])\n",
    "                max_area = max(area, max_area)\n",
    "        return max_area\n",
    "                    \n",
    "                    \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        u = list(range(m * n))\n",
    "        def find(i):\n",
    "            if u[i] != i:\n",
    "                u[i] = find(u[i])\n",
    "            return u[i]\n",
    "        area = [0] * (m * n)\n",
    "        mx = 0\n",
    "        for r, row in enumerate(grid):\n",
    "            for c, val in enumerate(row):\n",
    "                i = r * n + c \n",
    "                if val:\n",
    "                    u[i] = i\n",
    "                    area[i] = 1\n",
    "                    if r > 0 and grid[r - 1][c]:\n",
    "                        b = find(i - n)\n",
    "                        if b != u[i]:\n",
    "                            area[b] += area[u[i]]\n",
    "                            u[i] = b\n",
    "                    if c > 0 and grid[r][c - 1]:\n",
    "                        b = find(i - 1)\n",
    "                        if b != u[i]:\n",
    "                            area[b] += area[u[i]]\n",
    "                            u[find(i)] = b\n",
    "                    if area[u[find(i)]] > mx:\n",
    "                        mx = area[u[find(i)]]\n",
    "        return mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "\n",
    "\n",
    "        parent=list(range(m*n))\n",
    "\n",
    "        def find(i):\n",
    "            if i==parent[i]:return i\n",
    "            parent[i]=find(parent[i])\n",
    "            return parent[i]\n",
    "\n",
    "\n",
    "        def union(i,j):\n",
    "            rooti,rootj=find(i),find(j)\n",
    "            parent[rooti]=rootj\n",
    "\n",
    "\n",
    "        ll=[[1,0],[0,1]]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==0:continue\n",
    "\n",
    "                for ii,jj in ll:\n",
    "                    newi,newj=i+ii,j+jj\n",
    "                    if 0<=newi<m and 0<=newj<n and grid[newi][newj]:\n",
    "                        union(i*n+j,newi*n+newj)\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "        dicc=defaultdict(int)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    dicc[find(i*n+j)]+=1\n",
    "\n",
    "\n",
    "\n",
    "        return max(dicc.values()) if dicc.values() else 0\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        result = 0\n",
    "        row_num = len(grid)\n",
    "        col_num = len(grid[0])\n",
    "        adj_dict = {(i, j): set() for i in range(row_num) for j in range(col_num)}\n",
    "        neighbours = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "        for i in range(row_num):\n",
    "            for j in range(col_num):\n",
    "                if grid[i][j] == 0:\n",
    "                    continue\n",
    "                for a, b in neighbours:\n",
    "                    row = i + a\n",
    "                    col = j + b\n",
    "                    if 0 <= row < row_num and 0 <= col < col_num:\n",
    "                        if grid[row][col] == 0:\n",
    "                            continue\n",
    "                        adj_dict[(i, j)].add((row, col))\n",
    "                        adj_dict[(row, col)].add((i, j))\n",
    "\n",
    "        d = [[0 for i in range(col_num)] for j in range(row_num)]\n",
    "        g = 0\n",
    "        def bfs(u):\n",
    "            nonlocal d\n",
    "            nonlocal g\n",
    "            q = [u]\n",
    "            row_u, col_u = u\n",
    "            d[row_u][col_u] = 1\n",
    "            g += 1\n",
    "            while q:\n",
    "                u = q.pop()\n",
    "                row_u, col_u = u\n",
    "                for v in adj_dict[u]:\n",
    "                    row_v, col_v = v\n",
    "                    if d[row_v][col_v] == 0:\n",
    "                        g += 1\n",
    "                        d[row_v][col_v] = g\n",
    "                        q.append(v)\n",
    "\n",
    "\n",
    "        for i in range(row_num):\n",
    "            for j in range(col_num):\n",
    "                g = 0\n",
    "                if grid[i][j] == 0 or d[i][j] != 0:\n",
    "                    continue\n",
    "                bfs((i, j))\n",
    "        result = max(max(row) for row in d)\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxAreaOfIsland(self, grid: list[list[int]]) -> int:\r\n",
    "        m = len(grid)\r\n",
    "        n = len(grid[0])\r\n",
    "\r\n",
    "        def searchOne(searching, done, result):\r\n",
    "            if not searching:\r\n",
    "                return result\r\n",
    "            nonlocal m, n, grid\r\n",
    "            new_searching = []\r\n",
    "            for [r, c] in searching:\r\n",
    "                grid[r][c] = 0\r\n",
    "                for  [a, b] in [[-1, 0], [0, -1], [0, 1], [1, 0]]:\r\n",
    "                    rr, cc = r + a, c + b\r\n",
    "                    if [rr, cc] in done:\r\n",
    "                        continue\r\n",
    "                    if 0 <= rr < m and 0 <= cc < n:\r\n",
    "                        if grid[rr][cc] == 1:\r\n",
    "                            grid[rr][cc] = 0\r\n",
    "                            result += 1\r\n",
    "                            new_searching.append([rr, cc])\r\n",
    "                        done.append([rr, cc])\r\n",
    "            return searchOne(new_searching, done, result)\r\n",
    "\r\n",
    "        best = 0\r\n",
    "        for r in range(m):\r\n",
    "            for c in range(n):\r\n",
    "                if grid[r][c] == 1:\r\n",
    "                    area = searchOne([[r, c]], [[r, c]], 1)\r\n",
    "                    best = max(best, area)\r\n",
    "        return best\r\n",
    "                \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        visited = [[False]*col for _ in range(row)]\n",
    "        max_count = 0\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                count = 0\n",
    "                cur_count = self.dfs(i,j,visited,grid,row,col,count)\n",
    "                if cur_count >max_count:\n",
    "                    max_count = cur_count\n",
    "        return max_count\n",
    "\n",
    "    def dfs(self,x,y,visited,grid,row,col,count):\n",
    "        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "        if x< 0 or x>= row or y<0 or y>= col:\n",
    "            return count\n",
    "        if grid[x][y] != 1 or visited[x][y]:\n",
    "            return count\n",
    "        visited[x][y] = True\n",
    "        count +=1\n",
    "        for direction in directions:\n",
    "            count = self.dfs(x+direction[0],y+direction[1],visited,grid,row,col,count)\n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        n_row, n_col = len(grid), len(grid[0])\n",
    "        max_area = 0\n",
    "\n",
    "        def _dfs(row, col):\n",
    "            if row < 0 or row >= n_row or col < 0 or col >= n_col:\n",
    "                return 0\n",
    "            elif grid[row][col] == 0: return 0\n",
    "            grid[row][col] = 0\n",
    "            up = _dfs(row - 1, col)\n",
    "            down = _dfs(row + 1, col)\n",
    "            left = _dfs(row, col - 1)\n",
    "            right = _dfs(row, col + 1)\n",
    "            return up + down + left + right + 1\n",
    "\n",
    "        for row in range(n_row):\n",
    "            for col in range(n_col):\n",
    "                if grid[row][col] == 0: continue\n",
    "                max_area = max(max_area, _dfs(row, col))\n",
    "        return max_area\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        row, col = len(grid), len(grid[0])\n",
    "        ans = 0\n",
    "\n",
    "        def process(x, y):\n",
    "            if x<0 or x>=row or y<0 or y>=col: return 0\n",
    "            if grid[x][y] != 1: return 0\n",
    "\n",
    "            grid[x][y] = 2\n",
    "            return 1 + process(x+1, y) + process(x-1, y) + process(x, y+1) + process(x, y-1)\n",
    "\n",
    "            \n",
    "\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] == 1:\n",
    "                    temp = process(i,j)\n",
    "                    ans = max(ans, temp)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        result = 0\n",
    "\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        visited = [[0]*n for _ in range(m)]\n",
    "        maxresult =0\n",
    "        self.result = 0\n",
    "        dirs = [(0,-1),(-1,0),(0,1),(1,0)]\n",
    "\n",
    "        def dfs(x,y):\n",
    "            visited[x][y] = 1 \n",
    "            self.result +=1\n",
    "            for a, b  in dirs:\n",
    "                nextx = x+a\n",
    "                nexty = y+b\n",
    "                if nextx < 0 or nexty < 0 or nextx >=m or nexty >=n:\n",
    "                    continue\n",
    "                if visited[nextx][nexty] == 0  and grid[nextx][nexty] ==1:\n",
    "                    dfs(nextx,nexty)\n",
    "              \n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if visited[i][j] == 0 and grid[i][j] ==1:\n",
    "                     self.result = 0\n",
    "                     dfs(i,j)\n",
    "                     maxresult=max(maxresult,self.result)\n",
    "        return maxresult\n",
    "                \n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        self.m = len(grid)\n",
    "        self.n = len(grid[0])\n",
    "\n",
    "        for i in range(self.m):\n",
    "            for j in range(self.n):\n",
    "                if grid[i][j] == 1:\n",
    "                    res = max(res, self.dfs(grid, i, j))\n",
    "\n",
    "        return res\n",
    "\n",
    "    def dfs(self, grid, i, j):\n",
    "        if i < 0 or i >= self.m or j < 0 or j >=self.n:\n",
    "            return 0\n",
    "\n",
    "        if grid[i][j] == 0:\n",
    "            return 0\n",
    "\n",
    "        grid[i][j] = 0\n",
    "        return self.dfs(grid, i-1, j) + self.dfs(grid, i+1, j) + self.dfs(grid, i, j-1) + self.dfs(grid, i, j+1) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        if len(grid) == 0:\n",
    "            return 0\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 1:\n",
    "                    area = self.dfs(i, j, grid)\n",
    "                    ans = max(ans, area)\n",
    "        return ans\n",
    "\n",
    "    def dfs(self, i, j, grid):\n",
    "        if i < 0 or i == len(grid) or j < 0 or j == len(grid[0]) or grid[i][j] == 0:\n",
    "            return 0\n",
    "        \n",
    "        grid[i][j] = 0  # mark visited sites\n",
    "        return 1 + self.dfs(i+1, j, grid) +  self.dfs(i-1, j, grid) \\\n",
    "               + self.dfs(i, j+1, grid) + self.dfs(i, j-1, grid)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        dp = [[False]*n for _ in range(m)]\n",
    "\n",
    "        def dfs(x,y,cnt):\n",
    "            # print(1)\n",
    "            # print(x,y)\n",
    "            # print(dp[x][y])\n",
    "            if dp[x][y]:\n",
    "                return cnt\n",
    "            cnt += 1\n",
    "            dp[x][y] = True\n",
    "\n",
    "            dire = ((x-1,y),(x,y+1),(x+1,y),(x,y-1))#上右下左\n",
    "            for nx, ny in dire:\n",
    "                # print(nx,ny)\n",
    "                if nx >= 0 and nx < m and ny >= 0 and ny < n:\n",
    "                    if grid[nx][ny] == 1:\n",
    "                        cnt = dfs(nx,ny,cnt)\n",
    "            return cnt\n",
    "\n",
    "        # cnt = 0\n",
    "        # cnt = dfs(0,7,cnt)\n",
    "        # print(cnt)\n",
    "            \n",
    "\n",
    "        cnt_list = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    continue\n",
    "                else:\n",
    "                    if not dp[i][j]:\n",
    "                        cnt = 0\n",
    "                        cnt = dfs(i,j,cnt)\n",
    "                        cnt_list.append(cnt)\n",
    "        if not cnt_list:\n",
    "            return 0\n",
    "        else:\n",
    "            return max(cnt_list)\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "        \n",
    "        max_area = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if not visited[i][j] and grid[i][j] == 1:\n",
    "                    area = self.dfs(grid, visited, m, n, i, j)\n",
    "                    max_area = max(max_area, area)\n",
    "        return max_area\n",
    "                    \n",
    "    \n",
    "    def dfs(self, grid, visited, m, n, x, y):\n",
    "        visited[x][y] += 1\n",
    "        area = 1\n",
    "        \n",
    "        directions = [[0, -1], [0, 1], [1, 0], [-1, 0]]\n",
    "        for d in directions:\n",
    "            next_x, next_y = x + d[0], y + d[1]\n",
    "            if (0 <= next_x < m and \n",
    "                0 <= next_y < n and \n",
    "                grid[next_x][next_y] == 1 and\n",
    "                not visited[next_x][next_y]):\n",
    "                area += self.dfs(grid, visited, m, n, next_x, next_y)\n",
    "        return area\n",
    "                \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.count = 0\n",
    "\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        if not grid:\n",
    "            return 0\n",
    "        result = 0\n",
    "        m =len(grid)\n",
    "        n = len(grid[0])\n",
    "        visited= [[False]*n for _ in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1 and not visited[i][j]:\n",
    "                    self.count = 0\n",
    "                    self.dfs(grid, visited, i, j)\n",
    "                    result = max(result, self.count)\n",
    "\n",
    "        return result\n",
    "\n",
    "\n",
    "\n",
    "    def dfs(self, grid, visited, x, y):\n",
    "        if grid[x][y] == 0 or visited[x][y]:\n",
    "            return \n",
    "        visited[x][y] = True\n",
    "        self.count += 1\n",
    "        for new_x,new_y in [(x+1, y), (x-1, y), (x, y-1), (x, y+1)]:\n",
    "            if 0 <= new_x < len(grid) and 0 <= new_y < len(grid[0]):\n",
    "                self.dfs(grid, visited, new_x, new_y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        total_res = 0\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                res = 0\n",
    "                list1 = []\n",
    "                if grid[i][j] == 1:\n",
    "                    res+=1\n",
    "                    grid[i][j] = 0\n",
    "                    list1.append((i,j))\n",
    "                    while list1:\n",
    "                        cur_i,cur_j = list1.pop(0)\n",
    "                        for x,y in [(1,0),(-1,0),(0,1),(0,-1)]:\n",
    "                            temp_i = cur_i+x\n",
    "                            temp_j = cur_j+y\n",
    "                            if 0<=temp_i and temp_i < row and 0<=temp_j and temp_j<col and grid[temp_i][temp_j] == 1:\n",
    "                                grid[temp_i][temp_j] = 0\n",
    "                                res +=1\n",
    "                                list1.append((temp_i,temp_j))\n",
    "                total_res = max(res,total_res)\n",
    "        return total_res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        q = collections.deque()\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 1:\n",
    "                    cur = 1\n",
    "                    grid[i][j] = 0\n",
    "                    q.append([i, j])\n",
    "                    while q:\n",
    "                        x, y = q.popleft()\n",
    "                        if x > 0 and grid[x - 1][y] == 1:\n",
    "                            cur += 1\n",
    "                            grid[x - 1][y] = 0\n",
    "                            q.append([x - 1, y])\n",
    "                        if x < len(grid) - 1 and grid[x + 1][y] == 1:\n",
    "                            cur += 1\n",
    "                            grid[x + 1][y] = 0\n",
    "                            q.append([x + 1, y])\n",
    "                        if y > 0 and grid[x][y - 1] == 1:\n",
    "                            cur += 1\n",
    "                            grid[x][y - 1] = 0\n",
    "                            q.append([x, y - 1])\n",
    "                        if y < len(grid[0]) - 1 and grid[x][y + 1] == 1:\n",
    "                            cur += 1\n",
    "                            grid[x][y + 1] = 0\n",
    "                            q.append([x, y + 1])\n",
    "                    ans = max(ans, cur)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        maxarea=0\n",
    "        area=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    grid[i][j]=0\n",
    "                    area+=1\n",
    "                    q=collections.deque([(i,j)])\n",
    "                    while q:\n",
    "                        x,y=q.popleft()\n",
    "                        for dx,dy in [(0,1),(0,-1),(-1,0),(1,0)]:\n",
    "                            if 0<=x+dx<m and 0<=y+dy<n and grid[x+dx][y+dy]==1:\n",
    "                                area+=1\n",
    "                                grid[x+dx][y+dy]=0\n",
    "                                q.append((x+dx,y+dy))\n",
    "                    maxarea=max(maxarea,area)\n",
    "                    area=0\n",
    "        return maxarea\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        res = 0\n",
    "        def bfs(i, j):\n",
    "            deque = [(i, j)]\n",
    "            area = 1\n",
    "            grid[i][j] = 0\n",
    "            while deque:\n",
    "                old_x, old_y = deque.pop(0)\n",
    "                for x, y in directions:\n",
    "                    nx, ny = old_x + x, old_y + y\n",
    "                    if 0 <= nx < row and 0 <= ny < col:\n",
    "                        if grid[nx][ny] == 1:\n",
    "                            deque.append((nx, ny))\n",
    "                            area += 1\n",
    "                            grid[nx][ny] = 0\n",
    "            return area\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] == 1:\n",
    "                    area = bfs(i, j)\n",
    "                    res = max(res, area)\n",
    "        return res\n",
    "                \n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        self.grid = grid\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        self.m = m\n",
    "        self.n = n\n",
    "        self.res = 0\n",
    "        self.visited = [[0]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if self.grid[i][j] == 1 and self.visited[i][j] == 0:\n",
    "                    self.bfs(i, j)\n",
    "        return self.res\n",
    "\n",
    "    def bfs(self, x, y):\n",
    "        ground = 1\n",
    "        self.visited[x][y] = 1\n",
    "        nodeList = [(x, y)]\n",
    "        while len(nodeList) > 0:\n",
    "            length = len(nodeList)\n",
    "            for i in range(length):\n",
    "                x, y = nodeList.pop(0)\n",
    "                for nx, ny in [(x, y - 1), (x, y + 1), (x - 1, y), (x + 1, y)]:\n",
    "                    if nx >= 0 and nx < self.m and ny >=0 and ny < self.n and self.visited[nx][ny] == 0 and self.grid[nx][ny] == 1:\n",
    "                        self.visited[nx][ny] = 1\n",
    "                        nodeList.append((nx, ny))\n",
    "                        ground += 1\n",
    "        self.res = max(self.res , ground)\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "    m, n = len(grid), len(grid[0])\n",
    "    mk = [[0] * n for _ in range(m)]\n",
    "    def chk(aR, aC):\n",
    "      mk[aR][aC] = 1\n",
    "      ret = 1\n",
    "      q = [(aR, aC)]\n",
    "      while len(q) > 0:\n",
    "        r, c = q.pop(0)\n",
    "        for ri, ci in ((-1, 0), (0, -1), (1, 0), (0, 1)):\n",
    "          nr, nc = r + ri, c + ci\n",
    "          if nr >=0 and nr < m and nc >= 0 and nc < n:\n",
    "            if 1 == grid[nr][nc] and 0 == mk[nr][nc]:\n",
    "              mk[nr][nc] = 1\n",
    "              ret += 1\n",
    "              q.append((nr, nc))\n",
    "      return ret\n",
    "    ret = 0\n",
    "    for i in range(m):\n",
    "      for j in range(n):\n",
    "        if 1 == grid[i][j] and 0 == mk[i][j]:\n",
    "          ret = max(ret, chk(i, j))\n",
    "    return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        for i, l in enumerate(grid):\n",
    "            for j, n in enumerate(l):\n",
    "                cur = 0\n",
    "                q = collections.deque([(i, j)])\n",
    "                while q:\n",
    "                    cur_i, cur_j = q.popleft()\n",
    "                    if cur_i < 0 or cur_j < 0 or cur_i == len(grid) or cur_j == len(grid[0]) or grid[cur_i][cur_j] != 1:\n",
    "                        continue\n",
    "                    cur += 1\n",
    "                    grid[cur_i][cur_j] = 0\n",
    "                    for di, dj in [[0,1], [0,-1], [1, 0], [-1, 0]]:\n",
    "                        next_i, next_j = cur_i + di, cur_j + dj\n",
    "                        q.append((next_i, next_j))\n",
    "                ans = max(ans, cur)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        \n",
    "\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "\n",
    "        dirs = [[0,1],[0,-1],[1,0],[-1,0]]\n",
    "        \n",
    "        res = []\n",
    "\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "            \n",
    "                queue = collections.deque()\n",
    "\n",
    "                queue.append([i,j])\n",
    "                area = 0\n",
    "\n",
    "                while queue:\n",
    "                    x,y = queue.popleft()\n",
    "                    if grid[x][y]:\n",
    "                        area+=1             #area面积不要加两次\n",
    "                        grid[x][y] = 0\n",
    "\n",
    "                        for dx,dy in dirs:\n",
    "                            cx = x+dx\n",
    "                            cy = y+dy\n",
    "\n",
    "                            if cx>=0 and cx<row and cy>=0 and cy<col and grid[cx][cy]:\n",
    "                                queue.append([cx,cy])\n",
    "                \n",
    "                \n",
    "                res.append(area)\n",
    "\n",
    "        return max(res)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "##        dirs=[[0,-1],[-1,0],[0,1],[1,0]]\n",
    "##        temp = [0]\n",
    "#        row = len(grid)\n",
    "#        col = len(grid[0])\n",
    "\n",
    "#        def dfs(i,j):\n",
    "\n",
    "            \n",
    "#            if i>=0 and i<row and j>=0 and j<col and grid[i][j]==1:\n",
    "#                grid[i][j] = 0\n",
    "#                temp[-1] +=1\n",
    "#                for di,dj in dirs:\n",
    "#                    dfs(i+di,j+dj)\n",
    "#            else:\n",
    "#                return\n",
    "        \n",
    "#        result = [0]\n",
    "#        for i in range(row):\n",
    "#            for j in range(col):\n",
    "#                if grid[i][j]==1:\n",
    "#                    temp[-1] = 0\n",
    "#                    dfs(i,j)\n",
    "#                    result.append(temp[-1])\n",
    "        \n",
    "#        return max(result)\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: [[int]]) -> int:\n",
    "        def inqueue(q_0:deque, q_1:deque, p:[int,int], grid) -> int:\n",
    "            status = 0\n",
    "            if grid[p[0]][p[1]] == 0:\n",
    "                q_0.append(p)\n",
    "            elif grid[p[0]][p[1]] == 1:\n",
    "                q_1.append(p)\n",
    "                status = 1\n",
    "            grid[p[0]][p[1]] = 2\n",
    "            return status\n",
    "    \n",
    "        def inque_nbh(q_0:deque, q_1:deque, p:[int,int], length:int, width:int, grid, m:int) -> int:\n",
    "            row,column = p[0],p[1]\n",
    "            if row != 0:\n",
    "                if inqueue(q_0, q_1, [row - 1, column], grid):\n",
    "                    m = find(q_0, q_1, length, width, grid, m)\n",
    "            if row != width - 1:\n",
    "                if inqueue(q_0, q_1, [row + 1, column], grid):\n",
    "                    m = find(q_0, q_1, length, width, grid, m)\n",
    "            if column != 0:\n",
    "                if inqueue(q_0, q_1, [row, column - 1], grid):\n",
    "                    m = find(q_0, q_1, length, width, grid, m)\n",
    "            if column != length - 1:\n",
    "                if inqueue(q_0, q_1, [row, column + 1], grid):\n",
    "                    m = find(q_0, q_1, length, width, grid, m)\n",
    "            return m\n",
    "\n",
    "        def find(q_0:deque, q_1:deque, length:int, width:int, grid, square_max:int) -> int:\n",
    "            square = 0\n",
    "            while q_1:\n",
    "                a = q_1.popleft()\n",
    "                square = square + 1\n",
    "                row,column = a[0],a[1]\n",
    "                if row != 0:\n",
    "                    inqueue(q_0, q_1, [row - 1, column], grid)\n",
    "                if row != width - 1:\n",
    "                    inqueue(q_0, q_1, [row + 1, column], grid)\n",
    "                if column != 0:\n",
    "                    inqueue(q_0, q_1, [row, column - 1], grid)\n",
    "                if column != length - 1:\n",
    "                    inqueue(q_0, q_1, [row, column + 1], grid)\n",
    "\n",
    "            if square > square_max:\n",
    "                square_max = square\n",
    "            return square_max\n",
    "\n",
    "\n",
    "        q_0 = deque([])\n",
    "        q_1 = deque([])\n",
    "\n",
    "        square_max = 0\n",
    "\n",
    "        q = inqueue(q_0, q_1, [0,0], grid)\n",
    "        grid[0][0] = 2\n",
    "        length = len(grid[0])\n",
    "        width = len(grid)\n",
    "        while q_0 or q_1 :   #q0 和 q1均空，则检索结束\n",
    "            if q_1:\n",
    "                square_max = find(q_0, q_1, length, width, grid, square_max)\n",
    "            else:\n",
    "                a = q_0.popleft()\n",
    "                square_max = inque_nbh(q_0, q_1, a, length, width, grid, square_max)\n",
    "        return(square_max)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: [[int]]) -> int:\n",
    "        def inqueue(q_0:deque, q_1:deque, p:[int,int], grid) -> int:\n",
    "            status = 0\n",
    "            if grid[p[0]][p[1]] == 0:\n",
    "                q_0.append(p)\n",
    "            elif grid[p[0]][p[1]] == 1:\n",
    "                q_1.append(p)\n",
    "                status = 1\n",
    "            return status\n",
    "    \n",
    "        def inque_nbh(q_0:deque, q_1:deque, p:[int,int], length:int, width:int, grid, status:int) -> int:\n",
    "            row,column = p[0],p[1]\n",
    "            q = 0\n",
    "            if status == 0:\n",
    "                if q == 0 and row != 0:\n",
    "                    q = inqueue(q_0, q_1, [row - 1, column], grid)\n",
    "                    grid[row - 1][column] = 2\n",
    "                if q == 0 and row != width - 1:\n",
    "                    q = inqueue(q_0, q_1, [row + 1, column], grid)\n",
    "                    grid[row + 1][column] = 2\n",
    "                if q == 0 and column != 0:\n",
    "                    q = inqueue(q_0, q_1, [row, column - 1], grid)\n",
    "                    grid[row][column - 1] = 2\n",
    "                if q == 0 and column != length - 1:\n",
    "                    q = inqueue(q_0, q_1, [row, column + 1], grid)\n",
    "                    grid[row][column + 1] = 2\n",
    "            else:\n",
    "                if row != 0:\n",
    "                    inqueue(q_0, q_1, [row - 1, column], grid)\n",
    "                    grid[row - 1][column] = 2\n",
    "                if row != width - 1:\n",
    "                    inqueue(q_0, q_1, [row + 1, column], grid)\n",
    "                    grid[row + 1][column] = 2\n",
    "                if column != 0:\n",
    "                    inqueue(q_0, q_1, [row, column - 1], grid)\n",
    "                    grid[row][column - 1] = 2\n",
    "                if column != length - 1:\n",
    "                    inqueue(q_0, q_1, [row, column + 1], grid)\n",
    "                    grid[row][column + 1] = 2\n",
    "            return q\n",
    "\n",
    "\n",
    "        q_0 = deque([])\n",
    "        q_1 = deque([])\n",
    "        square = 0\n",
    "        square_max = 0\n",
    "        q = inqueue(q_0,q_1, [0,0], grid)\n",
    "        grid[0][0] = 2\n",
    "        length = len(grid[0])\n",
    "        width = len(grid)\n",
    "        while q_0 or q_1 :   #q0 和 q1均空，则检索结束\n",
    "            if q_1:\n",
    "                a = q_1.popleft()\n",
    "                square = square + 1\n",
    "                inque_nbh(q_0, q_1, a, length, width, grid, 1)\n",
    "\n",
    "            else:\n",
    "                if square > square_max:\n",
    "                    square_max = square\n",
    "                square = 0\n",
    "                a = q_0.popleft()\n",
    "                q = inque_nbh(q_0, q_1, a, length, width, grid, 0)\n",
    "                if q == 1:\n",
    "                    q_0.appendleft(a)\n",
    "\n",
    "        if square > square_max:\n",
    "            square_max = square\n",
    "        return(square_max)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: [[int]]) -> int:\n",
    "        union = Union(grid)\n",
    "        forwards = [[1, 0], [-1, 0], [0, 1], [0, -1]]\n",
    "        for row in range(len(grid)):\n",
    "            for col in range(len(grid[0])):\n",
    "                if grid[row][col] == 1:\n",
    "                    for forward in forwards:\n",
    "                        tx, ty = row + forward[0], col + forward[1]\n",
    "                        if 0 <= tx < len(grid) and 0 <= ty < len(grid[0]) and grid[tx][ty] == 1:\n",
    "                            union.union(row * len(grid[0]) + col, tx * len(grid[0]) + ty)\n",
    "        res = 0\n",
    "        for row in range(len(grid)):\n",
    "            for col in range(len(grid[0])):\n",
    "                idx = row * len(grid[0]) + col\n",
    "                if union.find(idx) == idx:\n",
    "                    res = max(res, union.rank[union.find(idx)])\n",
    "        return res\n",
    "\n",
    "\n",
    "class Union:\n",
    "    def __init__(self, grid: [[int]]) -> None:\n",
    "        rows, cols = len(grid), len(grid[0])\n",
    "        self.rows, self.cols = rows, cols\n",
    "        self.parent = [i for i in range(self.rows * self.cols)]\n",
    "        self.rank = [0 for i in range(self.rows * self.cols)]\n",
    "        for row in range(rows):\n",
    "            for col in range(cols):\n",
    "                if grid[row][col] == 1:\n",
    "                    self.rank[row * cols + col] = 1\n",
    "\n",
    "    def find(self, x):\n",
    "        while x != self.parent[x]:\n",
    "            x = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if x == y:\n",
    "            return\n",
    "        if self.rank[x] < self.rank[y]:\n",
    "            self.parent[x] = y\n",
    "            self.rank[y] += self.rank[x]\n",
    "        elif self.rank[x] > self.rank[y]:\n",
    "            self.parent[y] = x\n",
    "            self.rank[x] += self.rank[y]\n",
    "        elif x < y:\n",
    "            self.parent[y] = x\n",
    "            self.rank[x] += self.rank[y]\n",
    "        else:\n",
    "            self.parent[x] = y\n",
    "            self.rank[y] += self.rank[x]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: [[int]]) -> int:\n",
    "        def inqueue(q_0:deque, q_1:deque, p:[int,int], grid) -> int:\n",
    "            status = 0\n",
    "            if grid[p[0]][p[1]] == 0:\n",
    "                q_0.append(p)\n",
    "                status = 0\n",
    "            elif grid[p[0]][p[1]] == 1:\n",
    "                q_1.append(p)\n",
    "                status = 1\n",
    "            return status\n",
    "    \n",
    "        def inque_nbh(q_0:deque, q_1:deque, p:[int,int], length:int, width:int, grid, status:int) -> int:\n",
    "            row,column = p[0],p[1]\n",
    "            q = 0\n",
    "            if status == 0:\n",
    "                if q == 0 and row != 0:\n",
    "                    q = inqueue(q_0, q_1, [row - 1, column], grid)\n",
    "                    grid[row - 1][column] = 2\n",
    "                if q == 0 and row != width - 1:\n",
    "                    q = inqueue(q_0, q_1, [row + 1, column], grid)\n",
    "                    grid[row + 1][column] = 2\n",
    "                if q == 0 and column != 0:\n",
    "                    q = inqueue(q_0, q_1, [row, column - 1], grid)\n",
    "                    grid[row][column - 1] = 2\n",
    "                if q == 0 and column != length - 1:\n",
    "                    q = inqueue(q_0, q_1, [row, column + 1], grid)\n",
    "                    grid[row][column + 1] = 2\n",
    "            else:\n",
    "                if row != 0:\n",
    "                    inqueue(q_0, q_1, [row - 1, column], grid)\n",
    "                    grid[row - 1][column] = 2\n",
    "                if row != width - 1:\n",
    "                    inqueue(q_0, q_1, [row + 1, column], grid)\n",
    "                    grid[row + 1][column] = 2\n",
    "                if column != 0:\n",
    "                    inqueue(q_0, q_1, [row, column - 1], grid)\n",
    "                    grid[row][column - 1] = 2\n",
    "                if column != length - 1:\n",
    "                    inqueue(q_0, q_1, [row, column + 1], grid)\n",
    "                    grid[row][column + 1] = 2\n",
    "            return q\n",
    "\n",
    "\n",
    "        q_0 = deque([])\n",
    "        q_1 = deque([])\n",
    "        square = 0\n",
    "        square_max = 0\n",
    "        q = inqueue(q_0,q_1, [0,0], grid)\n",
    "        grid[0][0] = 2\n",
    "        length = len(grid[0])\n",
    "        width = len(grid)\n",
    "        while q_0 or q_1 :   #q0 和 q1均空，则检索结束\n",
    "            if q_1:\n",
    "                a = q_1.popleft()\n",
    "                square = square + 1\n",
    "                q = inque_nbh(q_0, q_1, a, length, width, grid, 1)\n",
    "\n",
    "            else:\n",
    "                if square > square_max:\n",
    "                    square_max = square\n",
    "                square = 0\n",
    "                a = q_0.popleft()\n",
    "                q = inque_nbh(q_0, q_1, a, length, width, grid, 0)\n",
    "                if q == 1:\n",
    "                    q_0.appendleft(a)\n",
    "\n",
    "        if square > square_max:\n",
    "            square_max = square\n",
    "        return(square_max)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        for i, l in enumerate(grid):\n",
    "            for j, n in enumerate(l):\n",
    "                cur = 0\n",
    "                stack = [(i, j)]\n",
    "                while stack:\n",
    "                    cur_i, cur_j = stack.pop()\n",
    "                    if cur_i < 0 or cur_j < 0 or cur_i == len(grid) or cur_j == len(grid[0]) or grid[cur_i][cur_j] != 1:\n",
    "                        continue\n",
    "                    cur += 1\n",
    "                    grid[cur_i][cur_j] = 0\n",
    "                    for di, dj in [[0, 1], [0, -1], [1, 0], [-1, 0]]:\n",
    "                        next_i, next_j = cur_i + di, cur_j + dj\n",
    "                        stack.append((next_i, next_j))\n",
    "                ans = max(ans, cur)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        row_num = len(grid)\n",
    "        col_num = len(grid[0])\n",
    "\n",
    "        parent = [i * col_num + j for i in range(row_num) for j in range(col_num)]\n",
    "        def find(i, j):\n",
    "            index = i * col_num + j\n",
    "            while parent[index] != index:\n",
    "                parent[index] = parent[parent[index]]\n",
    "                index = parent[index]\n",
    "            return index\n",
    "        \n",
    "        def join(i1, j1, i2, j2):\n",
    "            parent[find(i1, j1)] = find(i2, j2)\n",
    "        \n",
    "        flag = True\n",
    "        for i in range(row_num):\n",
    "            for j in range(col_num):\n",
    "                if grid[i][j] == 1:\n",
    "                    flag = False\n",
    "                    if i > 0 and grid[i-1][j] == 1:\n",
    "                        join(i, j, i-1, j)\n",
    "                    if i < row_num-1 and grid[i+1][j] == 1:\n",
    "                        join(i, j, i+1, j)\n",
    "                    if j > 0 and grid[i][j-1] == 1:\n",
    "                        join(i, j, i, j-1)\n",
    "                    if j < col_num-1 and grid[i][j+1] == 1:\n",
    "                        join(i, j, i, j+1)\n",
    "        if flag:\n",
    "            return 0\n",
    "        from collections import Counter\n",
    "        c = Counter([find(i, j) for i in range(row_num) for j in range(col_num)])\n",
    "        return c.most_common(1)[0][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        dp = [[False]*n for _ in range(m)]\n",
    "\n",
    "        ans = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    if not dp[i][j]:\n",
    "                        queue = [[i,j]]\n",
    "                        cnt = 1\n",
    "                        print(\"=====\")\n",
    "                        while queue:\n",
    "                            print(queue)\n",
    "                            x,y = queue.pop(0)\n",
    "                            dp[x][y] = True         \n",
    "                            dire = ((x-1,y),(x,y+1),(x+1,y),(x,y-1))\n",
    "                            for nx, ny in dire:\n",
    "                                if nx >= 0 and nx < m and ny >= 0 and ny < n:\n",
    "                                    if grid[nx][ny] == 1:\n",
    "                                        if not dp[nx][ny]:\n",
    "                                            cnt += 1\n",
    "                                            dp[nx][ny] = True\n",
    "                                            # if [nx,ny] not in queue:\n",
    "                                            queue.append([nx,ny])\n",
    "                        ans.append(cnt)\n",
    "        print(dp)\n",
    "        print(ans)\n",
    "        if ans:\n",
    "            return max(ans)\n",
    "        else:\n",
    "            return 0\n",
    "\n",
    "                            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "\n",
    "        def bfs(grid, i, j):\n",
    "            que = [(i, j)]\n",
    "            sub_res = 0\n",
    "            while que:\n",
    "                i, j = que.pop()\n",
    "                if 0<=i<m and 0<=j<n and grid[i][j] == 1:\n",
    "                    sub_res += 1\n",
    "                    grid[i][j] = 0\n",
    "                    que += [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]\n",
    "            return sub_res\n",
    "\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    tmp = bfs(grid, i, j)\n",
    "                    res = max(tmp, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                stack = [[i,j]]\n",
    "                cur = 0\n",
    "                while stack:\n",
    "                    cur_pos = stack.pop()\n",
    "                    if grid[cur_pos[0]][cur_pos[1]] == 0:\n",
    "                        continue\n",
    "                    cur += 1\n",
    "                    grid[cur_pos[0]][cur_pos[1]] = 0\n",
    "                    for action in [[0,1], [0,-1],[1,0],[-1,0]]:\n",
    "                        new_pos = [cur_pos[0] + action[0], cur_pos[1] + action[1]]\n",
    "                        if new_pos[0] >= 0 and new_pos[0] < len(grid) and new_pos[1] >= 0 and new_pos[1] < len(grid[0]):\n",
    "                            stack.append(new_pos)\n",
    "                ans = max(cur, ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        visited=[[0 for _ in range(n)]for _ in range(m)]\n",
    "        queue=[]\n",
    "        ans=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if visited[i][j]==0 and grid[i][j]==1:\n",
    "                    queue=[]\n",
    "                    queue.append([i,j])\n",
    "                    head=0\n",
    "                    \n",
    "                    while len(queue)-head!=0:\n",
    "                        t=queue[head]\n",
    "                        x=t[0]\n",
    "                        y=t[1]\n",
    "                        print(x,end=' ')\n",
    "                        print(y)\n",
    "                        visited[x][y]=1\n",
    "                        if x+1<m and grid[x+1][y]==1 and visited[x+1][y]==0:\n",
    "                            queue.append([x+1,y])\n",
    "                            visited[x+1][y]=1\n",
    "                        if x-1>=0 and grid[x-1][y]==1 and visited[x-1][y]==0:\n",
    "                            queue.append([x-1,y])\n",
    "                            visited[x-1][y]=1\n",
    "                        if y+1<n and grid[x][1+y]==1 and visited[x][y+1]==0:\n",
    "                            queue.append([x,1+y])\n",
    "                            visited[x][y+1]=1\n",
    "                        if y-1>=0 and grid[x][y-1]==1 and visited[x][y-1]==0:\n",
    "                            queue.append([x,y-1])\n",
    "                            visited[x][y-1]=1\n",
    "                        head+=1\n",
    "                    ans=max(ans,len(queue))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        choose = set()\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        for r in range(row):\n",
    "            for c in range(col):\n",
    "                if grid[r][c]==1:\n",
    "                    choose.add((r, c))\n",
    "        \n",
    "        def dfs(point):\n",
    "            x, y = point \n",
    "            if x >= row or y >= col or x<0 or y<0:\n",
    "                return 0\n",
    "            if grid[x][y]==0:\n",
    "                return 0 \n",
    "            grid[x][y] = 0\n",
    "            r = dfs((x+1, y))\n",
    "            l = dfs((x-1, y))\n",
    "            u = dfs((x, y+1))\n",
    "            d = dfs((x, y-1))\n",
    "            return r+l+u+d+1 \n",
    "        \n",
    "        max_ = 0\n",
    "        while choose:\n",
    "            p = choose.pop()\n",
    "            max_ = max(max_, dfs(p))\n",
    "        return max_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        m,n=len(grid),len(grid[0])\n",
    "\n",
    "        def bfs(grid,i,j):\n",
    "            deque = [[i,j]]\n",
    "            cnt = 0\n",
    "            while deque:\n",
    "                [i,j] = deque.pop()\n",
    "                if 0 <= i < m and 0 <= j < n and grid[i][j]==1:\n",
    "                    \n",
    "                    grid[i][j] = 0\n",
    "                    cnt+=1\n",
    "                    deque += [[i+1,j],[i-1,j],[i,j-1],[i,j+1]]\n",
    "            return cnt\n",
    "        # def bfs(grid,i,j):\n",
    "        #     deque = [[i,j]]\n",
    "        #     cnt = 0\n",
    "        #     while deque:\n",
    "        #         [i,j] = deque.pop(0)             # 这里目标只是为了将已经是1的节点出栈\n",
    "        #         if 0<=i<len(grid) and 0<=j<len(grid[0]) and grid[i][j] == 1:\n",
    "        #             grid[i][j]=0; cnt += 1       # 将访问过的节点置0避免重复访问，同时计数面积\n",
    "        #             deque += [[i+1,j],[i-1,j],[i,j+1],[i,j-1]]   # 记得其他节点入栈\n",
    "        #     return cnt\n",
    "\n",
    "\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0: continue\n",
    "                cnt = bfs(grid,i,j)\n",
    "                print(cnt)\n",
    "                ans = max(ans, cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.max_area = 0\n",
    "        self.visit = None\n",
    "\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0]) if grid else 0\n",
    "        self.visit = [[False for _ in range(m)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if not self.visit[i][j] and grid[i][j] == 1:\n",
    "                    self.max_area = max(self.max_area, self.dfs((i, j), grid))\n",
    "        return self.max_area\n",
    "    \n",
    "    def dfs(self, pos, grid):\n",
    "        i, j = pos\n",
    "        count = 1\n",
    "        self.visit[i][j] = True\n",
    "        self.max_area = max(self.max_area, count)        \n",
    "        if i + 1 < len(grid) and not self.visit[i + 1][j] and grid[i + 1][j] == 1:\n",
    "            count += self.dfs((i + 1, j), grid)\n",
    "        if i - 1 >= 0 and not self.visit[i - 1][j] and grid[i - 1][j] == 1:\n",
    "            count += self.dfs((i - 1, j), grid)\n",
    "        if j + 1 < len(grid[0]) and not self.visit[i][j + 1] and grid[i][j + 1] == 1:\n",
    "            count += self.dfs((i, j + 1), grid)\n",
    "        if j - 1 >= 0 and not self.visit[i][j - 1] and grid[i][j - 1] == 1:\n",
    "            count += self.dfs((i, j - 1), grid)\n",
    "        return count\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.visited = []\n",
    "        self.row = 0\n",
    "        self.col = 0\n",
    "        self.gird = []\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        self.row = len(grid)\n",
    "        self.col = len(grid[0])\n",
    "        self.gird = grid\n",
    "        # self.visited = [[False for _ in range(self.col)] for _ in range(self.row)]\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(self.row):\n",
    "            for j in range(self.col):\n",
    "                if grid[i][j] == 1:\n",
    "                    temp = self.dfs([i, j])\n",
    "                    ans = max(ans, temp)\n",
    "        return ans\n",
    "\n",
    "    def dfs(self, curr):\n",
    "        curr_row = curr[0]\n",
    "        curr_col = curr[1]\n",
    "\n",
    "        # self.visited[curr_row][curr_col] = True\n",
    "        self.gird[curr_row][curr_col] = 0\n",
    "        vaule = 0\n",
    "        is_in = False\n",
    "        for dir in [(0, 1), (0, -1), (1, 0), (-1, 0)]:\n",
    "            next_row = curr_row + dir[0]\n",
    "            next_col = curr_col + dir[1]\n",
    "\n",
    "            check_result = (0 <= next_row < self.row) and (0 <= next_col < self.col) and (\n",
    "                        self.gird[next_row][next_col] == 1)\n",
    "            if check_result:\n",
    "                temp = self.dfs([next_row, next_col])\n",
    "                vaule += temp\n",
    "                is_in = True\n",
    "\n",
    "        if is_in:\n",
    "            return vaule + 1\n",
    "        return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        seen = set()\n",
    "        return max(self.dfs(grid, r, c, seen) for r in range(len(grid)) for c in range(len(grid[0])))\n",
    "\n",
    "    def dfs(self, grid, r, c, seen):\n",
    "        if not (0 <= r < len(grid) and 0 <= c < len(grid[0]) and (r, c) not in seen and grid[r][c]):\n",
    "            return 0\n",
    "        seen.add((r, c))\n",
    "        return (1 + self.dfs(grid, 1 + r, c, seen) + self.dfs(grid, r, 1 + c, seen) + self.dfs(grid, r - 1, c, seen) + self.dfs(grid, r, c - 1, seen))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        row, col = len(grid), len(grid[0])\n",
    "        root = [0] * (row * col)\n",
    "\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                idx = i*col+j\n",
    "                root[idx] = idx\n",
    "        \n",
    "        def find(x):\n",
    "            r = root[x]\n",
    "            if r != x:\n",
    "                root[x] = find(r)\n",
    "            return root[x]\n",
    "            \n",
    "        \n",
    "        def merge(x1, x2):\n",
    "            root1, root2 = find(x1), find(x2)\n",
    "            if root1 != root2:\n",
    "                root[root1] = root2\n",
    "        \n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] == 1:\n",
    "                    idx = i*col+j\n",
    "                    if i > 0 and grid[i-1][j] == 1:\n",
    "                        merge(idx, idx-col)\n",
    "                    if j > 0 and grid[i][j-1] == 1:\n",
    "                        merge(idx, idx-1)\n",
    "\n",
    "        area = dict()\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] == 1:\n",
    "                    idx = i*col+j\n",
    "                    r = find(idx)\n",
    "                    if r in area:\n",
    "                        area[r] += 1\n",
    "                    else:\n",
    "                        area[r] = 1\n",
    "        \n",
    "        if area:\n",
    "            return max(area.values())\n",
    "        else:\n",
    "            return 0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        fa = [ [ (x,y) for y in range(n) ] for x in range(m) ]\n",
    "        S = [ [ 1 ] * n for _ in range(m) ]\n",
    "\n",
    "        def find(x, y):\n",
    "            if fa[x][y] == (x,y):\n",
    "                return fa[x][y]\n",
    "            fax, fay = fa[x][y]\n",
    "            fa[x][y] = find(fax, fay)\n",
    "            return fa[x][y]\n",
    "        \n",
    "        def merge(x1, y1, x2, y2):\n",
    "            fax1, fay1 = find(x1, y1)\n",
    "            fax2, fay2 = find(x2, y2)\n",
    "            if (fax1,fay1) == (fax2,fay2):\n",
    "                return S[fax1][fay1]\n",
    "            if S[x1][y1] <= S[x2][y2]:\n",
    "                fa[fax1][fay1] = (fax2, fay2)\n",
    "                S[fax2][fay2] += S[fax1][fay1]\n",
    "                return S[fax2][fay2]\n",
    "            else:\n",
    "                fa[fax2][fay2] = (fax1, fay1)\n",
    "                S[fax1][fay1] += S[fax2][fay2]\n",
    "                return S[fax1][fay1]\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    ans = max(ans, 1)\n",
    "                    if j - 1 >= 0 and grid[i][j-1] == 1:\n",
    "                        ans = max(ans, merge(i, j, i, j-1))\n",
    "                    if i - 1 >= 0 and grid[i-1][j] == 1:\n",
    "                        ans = max(ans, merge(i, j, i-1, j))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        def f(i, j):\n",
    "            return i * m + j\n",
    "        p = list(range(n * m))\n",
    "        sz = [0] * (n * m)\n",
    "\n",
    "        d = (0, -1, 0, 1, 0)\n",
    "\n",
    "        def find(x):\n",
    "            if p[x] != x:\n",
    "                p[x] = find(p[x])\n",
    "            return p[x]\n",
    "\n",
    "        def merge(x, y):\n",
    "            for dx, dy in pairwise(d):\n",
    "                tx, ty = x + dx, y + dy\n",
    "                if 0 <= tx < n and 0 <= ty < m and grid[tx][ty] == 1:\n",
    "                    p[find(f(x, y))] = find(f(tx, ty))\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 1:\n",
    "                    merge(i, j)\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 1:\n",
    "                    sz[find(f(i, j))] += 1\n",
    "                    \n",
    "        return max(sz)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "class Solution:\n",
    "    # 手撕三个版本，时间从快到慢分别是 uf, dfs, bfs\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dirs = [0, 1, 0, -1, 0]\n",
    "\n",
    "        def valid(x, y, m, n):\n",
    "            return x >= 0 and x < m and y >= 0 and y < n\n",
    "        \n",
    "        def dfs(grid, x, y, dirs, m, n):\n",
    "            grid[x][y] = 0\n",
    "            cnt = 1\n",
    "            for i in range(4):\n",
    "                x2, y2 = x + dirs[i], y + dirs[i + 1]\n",
    "                if valid(x2, y2, m, n) and grid[x2][y2] == 1:\n",
    "                    cnt += dfs(grid, x2, y2, dirs, m, n)\n",
    "            return cnt\n",
    "\n",
    "        def bfs(grid, x, y, dirs, m, n):\n",
    "            q = queue.Queue()\n",
    "            q.put((x, y))\n",
    "            grid[x][y] = 0\n",
    "            cnt = 0\n",
    "            while not q.empty():\n",
    "                x, y = q.get()\n",
    "                cnt += 1\n",
    "                for i in range(4):\n",
    "                    x2, y2 = x + dirs[i], y + dirs[i + 1]\n",
    "                    if valid(x2, y2, m, n) and grid[x2][y2] == 1:\n",
    "                        grid[x2][y2] = 0\n",
    "                        q.put((x2, y2))\n",
    "            return cnt\n",
    "\n",
    "        p, sizes = [0] * (m * n), [0] * (m * n)\n",
    "        for i in range(m * n):\n",
    "            p[i] = i\n",
    "\n",
    "        def find(x):\n",
    "            return x if x == p[x] else find(p[x])\n",
    "        def union(x, y):\n",
    "            rootX, rootY = find(x), find(y)\n",
    "            if rootX != rootY:\n",
    "                p[rootX] = rootY\n",
    "                sizes[rootY] += sizes[rootX]\n",
    "\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    x = i * n + j\n",
    "                    sizes[x] = 1\n",
    "                    if j > 0 and grid[i][j - 1] == 1: \n",
    "                        union(x, x - 1)\n",
    "                    if i > 0 and grid[i - 1][j] == 1: \n",
    "                        union(x, x - n)\n",
    "                    \n",
    "        ret = 0   \n",
    "        for i in range(m * n):\n",
    "            if p[i] == i:\n",
    "                ret = max(sizes[i], ret)\n",
    "        return ret\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        self.n1 = len(grid)\n",
    "        self.n2 = len(grid[0])\n",
    "        self.vis = [[0] * self.n2 for _ in range(self.n1)]\n",
    "        self.now = [0]\n",
    "        self.res = [0]\n",
    "        self.grid = grid\n",
    "        for i in range(self.n1):\n",
    "            for j in range(self.n2):\n",
    "                if self.grid[i][j] == 1 and self.vis[i][j] == 0:\n",
    "                    self.now[0] = 1\n",
    "                    self.vis[i][j] = 1\n",
    "                    self.dfs(i, j)\n",
    "        return self.res[0]\n",
    "    def check(self, i, j):\n",
    "        if self.grid[i][j] == 1 and self.vis[i][j] == 0:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "    def dfs(self, i, j):\n",
    "        if i > 0 and self.check(i - 1, j):\n",
    "            self.vis[i - 1][j] = 1\n",
    "            self.now[0] += 1\n",
    "            self.dfs(i - 1, j)\n",
    "        if i < self.n1 - 1 and self.check(i + 1, j):\n",
    "            self.vis[i + 1][j] = 1\n",
    "            self.now[0] += 1\n",
    "            self.dfs(i + 1 , j)\n",
    "        if j > 0 and self.check(i, j - 1):\n",
    "            self.vis[i][j - 1] = 1\n",
    "            self.now[0] += 1\n",
    "            self.dfs(i, j - 1)\n",
    "        if j < self.n2 - 1 and self.check(i, j + 1):\n",
    "            self.vis[i][j + 1] = 1\n",
    "            self.now[0] += 1\n",
    "            self.dfs(i, j + 1)\n",
    "        self.res[0] = max(self.res[0], self.now[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        \n",
    "        m,n = len(grid),len(grid[0])\n",
    "        res = 0\n",
    "\n",
    "        def dfs(i,j):\n",
    "            if not m>i>=0 or not n>j>=0 or grid[i][j]==0:\n",
    "                return 0\n",
    "            grid[i][j] = 0\n",
    "\n",
    "            return 1+dfs(i+1,j)+dfs(i-1,j)+dfs(i,j+1)+dfs(i,j-1)\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                res = max(res,dfs(i,j))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "class Solution:\n",
    "    # 手撕三个版本， dfs, bfs, uf\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dirs = [0, 1, 0, -1, 0]\n",
    "\n",
    "        def valid(x, y, m, n):\n",
    "            return x >= 0 and x < m and y >= 0 and y < n\n",
    "        \n",
    "        def dfs(grid, x, y, dirs, m, n):\n",
    "            grid[x][y] = 0\n",
    "            cnt = 1\n",
    "            for i in range(4):\n",
    "                x2, y2 = x + dirs[i], y + dirs[i + 1]\n",
    "                if valid(x2, y2, m, n) and grid[x2][y2] == 1:\n",
    "                    cnt += dfs(grid, x2, y2, dirs, m, n)\n",
    "            return cnt\n",
    "\n",
    "        def bfs(grid, x, y, dirs, m, n):\n",
    "            q = queue.Queue()\n",
    "            q.put((x, y))\n",
    "            grid[x][y] = 0\n",
    "            cnt = 0\n",
    "            while not q.empty():\n",
    "                x, y = q.get()\n",
    "                cnt += 1\n",
    "                for i in range(4):\n",
    "                    x2, y2 = x + dirs[i], y + dirs[i + 1]\n",
    "                    if valid(x2, y2, m, n) and grid[x2][y2] == 1:\n",
    "                        grid[x2][y2] = 0\n",
    "                        q.put((x2, y2))\n",
    "            return cnt\n",
    "\n",
    "        p, sizes = [0] * (m * n), [0] * (m * n)\n",
    "        for i in range(m * n):\n",
    "            p[i] = i\n",
    "\n",
    "        def find(x):\n",
    "            return x if x == p[x] else find(p[x])\n",
    "        def union(x, y):\n",
    "            rootX, rootY = find(x), find(y)\n",
    "            if rootX != rootY:\n",
    "                p[rootX] = rootY\n",
    "                sizes[rootY] += sizes[rootX]\n",
    "\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    x = i * n + j\n",
    "                    sizes[x] = 1\n",
    "                    if j > 0 and grid[i][j - 1] == 1: \n",
    "                        union(x, x - 1)\n",
    "                    if i > 0 and grid[i - 1][j] == 1: \n",
    "                        union(x, x - n)\n",
    "                    \n",
    "        ret = 0   \n",
    "        for i in range(m * n):\n",
    "            if p[i] == i:\n",
    "                ret = max(sizes[i], ret)\n",
    "        return ret\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        \n",
    "        def dfs(grid, cow, rol):\n",
    "            if cow<0 or rol<0 or cow>=len(grid) or rol>=len(grid[0]):\n",
    "                return 0\n",
    "            if grid[cow][rol]==1:\n",
    "                grid[cow][rol] = 0\n",
    "                left = dfs(grid, cow, rol-1)\n",
    "                right = dfs(grid, cow, rol+1)\n",
    "                up = dfs(grid, cow-1, rol)\n",
    "                down = dfs(grid, cow+1, rol)\n",
    "                return 1+left+right+up+down\n",
    "            else:\n",
    "                return 0\n",
    "        res = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j]:\n",
    "                    res = max(res, dfs(grid, i, j))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        def dfs(grid,i,j):\n",
    "            if i<0 or i>=len(grid) or j<0 or j>=len(grid[0]) or grid[i][j]==2 or grid[i][j]==0:\n",
    "                return 0\n",
    "            grid[i][j]=2\n",
    "            return 1+dfs(grid,i,j-1)+dfs(grid,i,j+1)+dfs(grid,i-1,j)+dfs(grid,i+1,j)\n",
    "        \n",
    "        result=0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j]==1:\n",
    "                    area=dfs(grid,i,j)\n",
    "                    if area>result:\n",
    "                        result=area\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        row, col = len(grid), len(grid[0])\n",
    "        def area(i, j) -> int:\n",
    "            if i < 0 or j < 0 or i >= row or j >= col or grid[i][j] == -1 or grid[i][j] == 0: return 0\n",
    "            grid[i][j] = -1\n",
    "            return 1 + area(i + 1, j) + area(i - 1, j) + area(i, j + 1) + area(i, j - 1) \n",
    "\n",
    "        ans = 0\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] == 1: ans = max(ans, area(i, j))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        flag = [[False for _ in range(len(grid[0]))] for _ in range(len(grid))]\n",
    "        def find(row,col):\n",
    "            if row < 0 or row >= len(grid) or col <0 or col >= len(grid[0]) or flag[row][col] or not grid[row][col]:\n",
    "                return 0\n",
    "            flag[row][col] = True\n",
    "            return 1 + find(row+1,col) + find(row-1,col) + find(row,col+1) + find(row,col-1)\n",
    "        res = 0\n",
    "        for row in range(len(grid)):\n",
    "            for col in range(len(grid[0])):\n",
    "                if grid[row][col]:\n",
    "                    res = max(res,find(row,col))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        seen = [[False] * n for _ in range(m)]\n",
    "\n",
    "        def dfs(i, j):\n",
    "            seen[i][j] = True\n",
    "            if grid[i][j] == 0:\n",
    "                return 0\n",
    "            grid[i][j] = 0\n",
    "            ans = 1\n",
    "            for di, dj in ((0, 1), (0, -1), (1, 0), (-1, 0)):\n",
    "                ni, nj = i + di, j + dj\n",
    "                if 0 <= ni < m and 0 <= nj < n and not seen[ni][nj]:\n",
    "                    ans += dfs(ni, nj)\n",
    "            return ans\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    ans = max(ans, dfs(i, j))\n",
    "                    # ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        ans = 0\n",
    "        dxy = [[-1, 0, 0, 1], [0, 1, -1, 0]]\n",
    "        def dfs(x: int, y: int) -> int:\n",
    "            grid[x][y] = 0\n",
    "            res = 1\n",
    "            for k in range(4):\n",
    "                xx, yy = x + dxy[0][k], y + dxy[1][k]\n",
    "                if xx >= 0 and xx < n and yy >= 0 and yy < m and grid[xx][yy] == 1:\n",
    "                    res += dfs(xx, yy)\n",
    "            return res\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 1:\n",
    "                    ans = max(ans, dfs(i, j))\n",
    "        return ans    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        choose = set()\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        for r in range(row):\n",
    "            for c in range(col):\n",
    "                if grid[r][c]==1:\n",
    "                    choose.add((r, c))\n",
    "        \n",
    "        def dfs(point):\n",
    "            x, y = point \n",
    "            if x >= row or y >= col or x<0 or y<0:\n",
    "                return 0\n",
    "            if grid[x][y]==0:\n",
    "                return 0 \n",
    "            if point in choose:\n",
    "                choose.remove(point)\n",
    "            grid[x][y] = 0\n",
    "            r = dfs((x+1, y))\n",
    "            l = dfs((x-1, y))\n",
    "            u = dfs((x, y+1))\n",
    "            d = dfs((x, y-1))\n",
    "            return r+l+u+d+1 \n",
    "        \n",
    "        max_ = 0\n",
    "        while choose:\n",
    "            p = choose.pop()\n",
    "            max_ = max(max_, dfs(p))\n",
    "        return max_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        max_area = 0\n",
    "        def recur(i,j,ans):\n",
    "            #递归出口\n",
    "            if grid[i][j] == 0: return 0\n",
    "            grid[i][j] =0\n",
    "            ans = 1\n",
    "            for x,y in (1,0), (0,1), (-1,0), (0,-1):\n",
    "                new_i, new_j = i+x, j+y\n",
    "                if new_i<m and new_i >=0 and new_j<n and new_j>=0 and grid[new_i][new_j]==1:\n",
    "                    ans += recur(new_i, new_j, ans)\n",
    "            return ans\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    max_area = max(max_area, recur(i,j,0))\n",
    "        return max_area\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                ans = max(ans, self.areaOfIsland(grid, i, j))\n",
    "        return ans\n",
    "\n",
    "\n",
    "    def areaOfIsland(self, grid: List[List[int]], x: int, y: int) -> int:\n",
    "        if x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0]) or grid[x][y] == 0:\n",
    "            return 0\n",
    "        \n",
    "        ans = 1\n",
    "        grid[x][y] = 0\n",
    "        dirctions = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        for i, j in dirctions:\n",
    "            ans += self.areaOfIsland(grid, x + i, y + j)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        x_dir = [1,-1,0,0]\n",
    "        y_dir = [0,0,1,-1]\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visit = [[0] * n for _ in range(m)]\n",
    "        def dfs(x,y):\n",
    "            if not(0 <= x < m and 0 <= y < n) or visit[x][y] or not grid[x][y]:\n",
    "                return 0\n",
    "            visit[x][y] = 1\n",
    "            ret = 1\n",
    "            for i in range(4):\n",
    "                ret += dfs(x+x_dir[i],y+y_dir[i])\n",
    "            return ret\n",
    "            \n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] and not visit[i][j]:\n",
    "                    ans = max(ans,dfs(i,j))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(grid,i,j,flg,n,m,count):\n",
    "            count += 1\n",
    "            flg[i][j] = False\n",
    "            if 0 < i and grid[i - 1][j] == 1 and flg[i - 1][j]:\n",
    "                count = dfs(grid,i -1,j,flg,n,m,count)\n",
    "            if i < m-1 and grid[i + 1][j] == 1 and flg[i + 1][j]:\n",
    "                count = dfs(grid,i + 1,j,flg,n,m,count)\n",
    "            if 0< j and grid[i][j-1] == 1 and flg[i][j - 1]:\n",
    "                count = dfs(grid,i,j - 1,flg,n,m,count)\n",
    "            if j < n-1 and grid[i][j+1] == 1 and flg[i][j + 1]:\n",
    "                count = dfs(grid,i,j + 1,flg,n,m,count)\n",
    "            print(count)\n",
    "            return count\n",
    "        flg = [[True for i in grid[0]]for i in grid]\n",
    "        plist = []\n",
    "        n = len(grid[0])\n",
    "        m = len(grid)\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[i])):\n",
    "                if grid[i][j] == 1 and flg[i][j]:\n",
    "                    count = 0\n",
    "                    l = dfs(grid,i,j, flg,n,m,count)\n",
    "                    plist.append(l)\n",
    "        \n",
    "        return max(plist) if plist else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        rem_mat = [[True] * len(grid[0]) for _ in range(len(grid))]\n",
    "        def dfs(i,j):\n",
    "            nonlocal ans_temp\n",
    "            dir = [(1,0),(-1,0),(0,1),(0,-1)]\n",
    "            if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]):\n",
    "                return\n",
    "            if grid[i][j] == 0 or rem_mat[i][j] == False:\n",
    "                return\n",
    "            if grid[i][j] == 1 and rem_mat[i][j] == True:\n",
    "                ans_temp += 1\n",
    "                rem_mat[i][j] = False\n",
    "                for m,n in dir:\n",
    "                    dfs(i+m,j+n)\n",
    "\n",
    "            \n",
    "\n",
    "        for i in range(0,len(grid)):\n",
    "            for j in range(0,len(grid[0])):\n",
    "                ans_temp = 0\n",
    "                dfs(i,j)\n",
    "                ans = max(ans_temp,ans)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        paces = [(0,1),(1,0),(0,-1),(-1,0)]\n",
    "        visited = [[0]* len(grid[0]) for _ in range(len(grid))]\n",
    "        def DFS(i,j):\n",
    "            visited[i][j] = 1\n",
    "            re = 1\n",
    "            for x,y in paces:\n",
    "                nxt_x , nxt_y = x + i,y + j\n",
    "                if 0 <= nxt_x < len(grid) and 0 <= nxt_y < len(grid[0]) and visited[nxt_x][nxt_y] == 0 and grid[nxt_x][nxt_y] == 1:\n",
    "                    re += DFS(nxt_x,nxt_y)\n",
    "            return re\n",
    "\n",
    "        visited = [[0]* len(grid[0]) for _ in range(len(grid))]\n",
    "        ans = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if visited[i][j] == 0 and grid[i][j] == 1:\n",
    "                    a = DFS(i,j)\n",
    "                    print(i,j,a)\n",
    "                    ans = max(ans,a)\n",
    "                else :\n",
    "                    visited[i][j] = 1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        used_diction = collections.Counter()\n",
    "        def dfs(i,j):\n",
    "            if used_diction[(i,j)]>0:\n",
    "                return 0 \n",
    "            if i>=len(grid):\n",
    "                return 0\n",
    "            if j>=len(grid[0]):\n",
    "                return 0\n",
    "            if i<0 or j<0:\n",
    "                return 0\n",
    "            if grid[i][j] ==0:\n",
    "                return 0\n",
    "            used_diction[(i,j)]+=1\n",
    "            return dfs(i+1, j)+dfs(i, j+1)+dfs(i-1, j)+ dfs(i, j-1)+1\n",
    "        \n",
    "        max_mj = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if used_diction[(i,j)]>0:\n",
    "                    continue\n",
    "                if grid[i][j] == 1:\n",
    "                    count = dfs(i, j)\n",
    "                    max_mj = max(max_mj, count)\n",
    "        return max_mj"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        def area(i,j):\n",
    "            if i<0 or i>=m or j<0 or j>=n:\n",
    "                return 0\n",
    "            if grid[i][j]!=1:\n",
    "                return 0\n",
    "            grid[i][j]=2\n",
    "            return 1+area(i,j+1)+area(i,j-1)+area(i-1,j)+area(i+1,j)\n",
    "        ans=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    a=area(i,j)\n",
    "                    ans=max(a,ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        res = 0\n",
    "\n",
    "        def dfs(i,j):\n",
    "            if 0 <= i < m and 0 <= j < n and grid[i][j] != 0:\n",
    "                grid[i][j] = 0\n",
    "                return 1 + dfs(i-1,j) + dfs(i+1,j) + dfs(i,j-1) + dfs(i,j+1)\n",
    "            return 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    res = max(res,dfs(i,j))\n",
    "                    \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        max_res = 0\n",
    "        def dfs(x, y):\n",
    "            if grid[x][y] == 1:\n",
    "                grid[x][y] = 0\n",
    "                num =1\n",
    "            else:\n",
    "                return 0\n",
    "\n",
    "            if x > 0:\n",
    "                num += dfs(x-1, y)\n",
    "            if x < m-1:\n",
    "                num += dfs(x+1, y)\n",
    "            if y > 0 :\n",
    "                num += dfs(x, y-1)\n",
    "            if y < n-1:\n",
    "                num += dfs(x, y+1)\n",
    "\n",
    "            return num\n",
    "            \n",
    "        for a in range(m):\n",
    "            for b in range(n):\n",
    "                if grid[a][b] == 1:\n",
    "                    res = dfs(a,b)\n",
    "                    max_res = max(max_res, res)\n",
    "        return max_res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        row, col = len(grid), len(grid[0])\n",
    "        ans = 0\n",
    "\n",
    "        def process(x, y):\n",
    "            if x <0 or x>=row or y<0 or y>= col: return 0\n",
    "            if grid[x][y] != 1: return 0\n",
    "            grid[x][y] = 2\n",
    "            \n",
    "            return 1 + process(x+1,y) + process(x-1, y) + process(x, y+1) + process(x, y-1)\n",
    "\n",
    "\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] == 1:\n",
    "                    temp = process(i, j)\n",
    "                    ans = max(ans, temp)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        def dfs(i, j):\n",
    "            if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == 0:\n",
    "                return 0\n",
    "            grid[i][j] = 0\n",
    "            return dfs(i-1, j) + dfs(i+1, j) + dfs(i, j-1) + dfs(i, j+1) + 1\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    res = max(res, dfs(i, j))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        row_num = len(grid)\n",
    "        col_num = len(grid[0])\n",
    "        def dfs(i, j):\n",
    "            if i < 0 or i > row_num-1 or j < 0 or j > col_num-1 or grid[i][j] == 0:\n",
    "                return 0\n",
    "            grid[i][j] = 0\n",
    "            return dfs(i+1, j) + dfs(i, j+1) + dfs(i-1, j) + dfs(i, j-1) + 1\n",
    "        \n",
    "        for i in range(row_num):\n",
    "            for j in range(col_num):\n",
    "                if grid[i][j] == 1:\n",
    "                    ans = max(ans, dfs(i, j))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        \n",
    "        def inject(i, j):\n",
    "            if i < 0 or i == len(grid) or j < 0 or j == len(grid[0]):\n",
    "                return 0\n",
    "            if grid[i][j] == 1:\n",
    "                grid[i][j] = 2\n",
    "                a1 = inject(i + 1, j)\n",
    "                a2 = inject(i - 1, j)\n",
    "                a3 = inject(i, j + 1)\n",
    "                a4 = inject(i, j - 1)\n",
    "                return a1 + a2 + a3 + a4 + 1\n",
    "            return 0\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 1:\n",
    "                    ans = max(inject(i, j), ans)\n",
    "                    \n",
    "        return ans\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        #每次dfs过程中记录面积\n",
    "        def dfs(i,j):\n",
    "            if 0<=i<m and 0<=j<n and grid[i][j]==1:\n",
    "                grid[i][j]=2\n",
    "                return 1+dfs(i-1,j)+dfs(i+1,j)+dfs(i,j-1)+dfs(i,j+1)\n",
    "            else:\n",
    "                return 0\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        ans=[]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    ans.append(dfs(i,j))\n",
    "        # return max(ans)  \n",
    "        return max(ans) if ans else 0#防止全是水，没有岛屿的情况"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        \n",
    "        dirs=[[0,-1],[-1,0],[0,1],[1,0]]\n",
    "        temp = [0]\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "\n",
    "        def dfs(i,j):\n",
    "\n",
    "            \n",
    "            if i>=0 and i<row and j>=0 and j<col and grid[i][j]==1:\n",
    "                grid[i][j] = 0\n",
    "                temp[-1] +=1\n",
    "                for di,dj in dirs:\n",
    "                    dfs(i+di,j+dj)\n",
    "            else:\n",
    "                return\n",
    "        \n",
    "        result = [0]\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j]==1:\n",
    "                    temp[-1] = 0\n",
    "                    dfs(i,j)\n",
    "                    result.append(temp[-1])\n",
    "        \n",
    "        return max(result)\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # DFS. Time O(mn) Space O(mn)\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]\n",
    "        # returns the size of the island which x, y belongs to\n",
    "        # and sinks the island\n",
    "        def dfs(x: int, y: int) -> int:\n",
    "            if grid[x][y] != 1: return 0\n",
    "            # for every place visited, change it to zero and never change it back\n",
    "            # this guarantees that every 1 is visited only once\n",
    "            grid[x][y] = 0\n",
    "            res = 1\n",
    "            for dx, dy in dirs:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < m and 0 <= ny < n:\n",
    "                    res += dfs(nx, ny)\n",
    "            return res\n",
    "        res = 0\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                res = max(res, dfs(x, y))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        ans = 0\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] == 1:\n",
    "                    area = self.dfs(grid, row, col, i, j)\n",
    "                    ans = max(ans, area)\n",
    "        return ans\n",
    "        \n",
    "    def dfs(self, grid, row, col, x, y):\n",
    "        if grid[x][y] == 0:\n",
    "            return 0\n",
    "        grid[x][y] = 2\n",
    "        area = 1\n",
    "        for dx, dy in [(-1,0), (0, -1), (0, 1), (1, 0)]:\n",
    "            xhat, yhat = x + dx, y + dy\n",
    "            if -1 < xhat < row and -1 < yhat < col and grid[xhat][yhat] == 1:\n",
    "                area += self.dfs(grid, row, col, xhat, yhat)\n",
    "        \n",
    "        return area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        maxArea = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 1:\n",
    "                    maxArea = max(maxArea, self.dfs(grid, i, j))\n",
    "        return maxArea\n",
    "\n",
    "    def dfs(self, grid, i, j) -> int:\n",
    "        if i < 0 or i >= len(grid):\n",
    "            return 0\n",
    "        if j < 0 or j >= len(grid[0]):\n",
    "            return 0\n",
    "        if grid[i][j] == 0:\n",
    "            return 0\n",
    "\n",
    "        area = 1\n",
    "        grid[i][j] = 0\n",
    "\n",
    "        area += self.dfs(grid, i+1, j)\n",
    "        area += self.dfs(grid, i, j+1)\n",
    "        area += self.dfs(grid, i-1, j)\n",
    "        area += self.dfs(grid, i, j-1)\n",
    "\n",
    "        return area\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.max_Area=0\n",
    "        self.area=0\n",
    "    def dfs(self,grid,i,j):\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        if i<0 or i>=m or j<0 or j>=n or grid[i][j]==0:\n",
    "            return\n",
    "        self.area+=1\n",
    "        grid[i][j]=0\n",
    "        self.dfs(grid,i+1,j)\n",
    "        self.dfs(grid,i,j+1)\n",
    "        self.dfs(grid,i-1,j)\n",
    "        self.dfs(grid,i,j-1)\n",
    "        \n",
    "\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    self.dfs(grid,i,j)\n",
    "                    self.max_Area=max(self.max_Area,self.area)\n",
    "                    self.area=0\n",
    "\n",
    "\n",
    "        return self.max_Area\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        # 地图尺寸\n",
    "        h, w = len(grid), len(grid[0])\n",
    "        # 探索方向\n",
    "        dirs = [[-1,0], [0,-1], [1,0],[0,1]]\n",
    "\n",
    "        def dfs(row, col, area):\n",
    "            # 填陆造海，来过的地方为0，防止dfs搜索回去\n",
    "            grid[row][col] = 0\n",
    "\n",
    "            # 判断四周\n",
    "            for r, c in dirs:\n",
    "                nrow, ncol = row+r, col+c\n",
    "                # 如果能到达新区域且新区域值为1\n",
    "                if 0 <= nrow < h and 0 <= ncol < w and grid[nrow][ncol]==1:\n",
    "                    # 岛屿面积+1\n",
    "                    area = dfs(nrow, ncol, area+1)\n",
    "            # 检查完四周返回岛屿面积\n",
    "            return area\n",
    "\n",
    "        ret = [] # 记录各个岛屿面积\n",
    "        island = 0 #记录岛屿个数\n",
    "        for row in range(h):\n",
    "            for col in range(w):\n",
    "                # 跳过0的地方，不需要搜\n",
    "                if grid[row][col] == 1:\n",
    "                    area = dfs(row, col, 1) # 注意这里是1，因为我们很确定这里有岛\n",
    "                    ret.append(area) # dfs结束说明搜完了一个岛\n",
    "                    island += 1\n",
    "\n",
    "        # 根据题意返回需要的量，这里题目要求的是面积\n",
    "        return max(ret) if ret else 0 \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        # 地图尺寸\n",
    "        h, w = len(grid), len(grid[0])\n",
    "        # 探索方向\n",
    "        dirs = [[-1,0], [0,-1], [1,0],[0,1]]\n",
    "\n",
    "        def dfs(row, col, area):\n",
    "            # 填陆造海，来过的地方为0，防止dfs搜索回去\n",
    "            grid[row][col] = 0\n",
    "\n",
    "            # 判断四周\n",
    "            for r, c in dirs:\n",
    "                nrow, ncol = row+r, col+c\n",
    "                # 如果能到达新区域且新区域值为1\n",
    "                if 0 <= nrow < h and 0 <= ncol < w and grid[nrow][ncol]==1:\n",
    "                    # 岛屿面积+1\n",
    "                    area = dfs(nrow, ncol, area+1)\n",
    "            # 检查完四周返回岛屿面积\n",
    "            return area\n",
    "\n",
    "        ret = [] # 记录各个岛屿面积\n",
    "        island = 0 #记录岛屿个数\n",
    "        for row in range(h):\n",
    "            for col in range(w):\n",
    "                # 跳过0的地方，不需要搜\n",
    "                if grid[row][col] == 1:\n",
    "                    area = dfs(row, col, 1) # 注意这里是1，因为我们很确定这里有岛\n",
    "                    ret.append(area) # dfs结束说明搜完了一个岛\n",
    "                    island += 1\n",
    "\n",
    "        # 根据题意返回需要的量，这里题目要求的是面积\n",
    "        print(island)\n",
    "        return max(ret) if ret else 0 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, grid, row, col):\n",
    "        dirs = [(0,1), (0,-1), (1,0), (-1,0)]\n",
    "        if grid[row][col]==0:\n",
    "            return 0\n",
    "        res = 1\n",
    "        grid[row][col] = 0\n",
    "        for x,y in dirs:\n",
    "            nx = row+x\n",
    "            ny = col+y\n",
    "            if nx<0 or nx>=len(grid) or ny<0 or ny>=len(grid[0]):\n",
    "                continue\n",
    "            res += self.dfs(grid, nx, ny)\n",
    "        return res\n",
    "\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    res = max(res, self.dfs(grid, i, j))\n",
    "        return res\n",
    "\n",
    "        # # BFS\n",
    "        # m, n = len(grid), len(grid[0])\n",
    "        # res = 0\n",
    "        # dirs = [(0,1), (0,-1), (1,0), (-1,0)]\n",
    "        # for i in range(m):\n",
    "        #     for j in range(n):\n",
    "        #         if grid[i][j]==1:\n",
    "        #             cur = 0\n",
    "        #             q = collections.deque([(i,j)])\n",
    "        #             while q:\n",
    "        #                 cur_x, cur_y = q.popleft()\n",
    "        #                 cur += 1\n",
    "        #                 grid[cur_x][cur_y] = 0\n",
    "        #                 for x, y in dirs:\n",
    "        #                     nx = cur_x + x\n",
    "        #                     ny = cur_y + y\n",
    "        #                     if nx<0 or ny<0 or nx>=m or ny>=n:\n",
    "        #                         continue\n",
    "        #                     q.append((nx,ny))\n",
    "        #             res = max(res, cur)\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def dfs(i, j, grid: List[List[int]]) -> int:\n",
    "    m = len(grid)\n",
    "    n = len(grid[0])\n",
    "    if (i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != 1):\n",
    "        return 0\n",
    "    grid[i][j] = -1\n",
    "    left = dfs(i - 1, j, grid)\n",
    "    right = dfs(i + 1, j, grid)\n",
    "    up = dfs(i, j + 1, grid)\n",
    "    down = dfs(i, j - 1, grid)\n",
    "    return 1 + left + right + up + down\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if(grid[i][j] == 1):\n",
    "                    count = dfs(i, j, grid)\n",
    "                    res = max(res, count)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: list[list[int]]) -> int:\n",
    "        maxarea = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j]==1:\n",
    "                    # 对这个陆地进行打击\n",
    "                    grid[i][j]=0\n",
    "                    # curarea = 1\n",
    "                    curarea = self.dfs(i,j,grid,1)\n",
    "                    if curarea>maxarea:\n",
    "                        maxarea=curarea\n",
    "        return maxarea\n",
    "\n",
    "\n",
    "    def dfs(self,x,y,grid,area):\n",
    "        dirs =  [(0,1),(0,-1),(-1,0),(1,0)]\n",
    "        for i in range(len(dirs)):\n",
    "            xn = x+dirs[i][0]\n",
    "            yn = y+dirs[i][1]\n",
    "            if xn>=0 and xn<len(grid) and yn>=0 and yn<len(grid[0]):\n",
    "                if grid[xn][yn]==1:\n",
    "                    area += 1\n",
    "                    grid[xn][yn]=0\n",
    "                    area = self.dfs(xn,yn,grid,area)\n",
    "        return area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(index_i, index_j):\n",
    "            if index_i < 0 or index_i >= len(grid):\n",
    "                return 0\n",
    "\n",
    "            if index_j < 0 or index_j >= len(grid[0]):\n",
    "                return 0\n",
    "\n",
    "            if grid[index_i][index_j] == 1:\n",
    "                grid[index_i][index_j] = 0\n",
    "                resp = (\n",
    "                    1\n",
    "                    + dfs(index_i - 1, index_j)\n",
    "                    + dfs(index_i + 1, index_j)\n",
    "                    + dfs(index_i, index_j + 1)\n",
    "                    + dfs(index_i, index_j - 1)\n",
    "                )\n",
    "                return resp\n",
    "\n",
    "            else:\n",
    "                return 0\n",
    "\n",
    "        max_size = 0\n",
    "\n",
    "        for index_i, line in enumerate(grid):\n",
    "            for index_j in range(len(line)):\n",
    "                if grid[index_i][index_j] == 1:\n",
    "                    max_size = max(max_size, dfs(index_i, index_j))\n",
    "\n",
    "        return max_size\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 1:\n",
    "                    res = max(res, self.dfs(i, j, grid))\n",
    "        return res\n",
    "\n",
    "    def dfs(self, i, j, grid):\n",
    "        if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == 0:\n",
    "            return 0\n",
    "        grid[i][j] = 0\n",
    "        return 1+self.dfs(i-1, j, grid)+self.dfs(i+1, j, grid)+self.dfs(i, j-1, grid)+self.dfs(i, j+1, grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 岛屿系列题目的核心就是考察：DFS BFS算法遍历二维数组\n",
    "# https://labuladong.github.io/algo/di-san-zha-24031/bao-li-sou-96f79/yi-wen-mia-4f482/\n",
    "# 这题的大体思路和之前完全一样，只不过 dfs 函数淹没岛屿的同时，还应该想办法记录这个岛屿的面积。\n",
    "# 我们可以给 dfs 函数设置返回值，记录每次淹没的陆地的个数\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1: # 土地\n",
    "                    # res += 1 # 这里不能res+1了，因为之前算的是岛屿个数，而这里是求最大岛屿面积\n",
    "                    # 去淹没上下左右的土地\n",
    "                    cur = self.dfs(grid, i, j)\n",
    "                    res = max(res, cur)\n",
    "\n",
    "        return res\n",
    "    \n",
    "    def dfs(self, grid, i, j):\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        # 终止条件\n",
    "        if i < 0 or j < 0 or i >= m or j >= n:\n",
    "            return 0 # 这里要返回0，而不是像前面那样直接return啥也不返回了。因为返回0，下面的num要加上的\n",
    "\n",
    "        # 终止条件\n",
    "        if grid[i][j] == 0: # 海水\n",
    "            return 0 # 这里要返回0，而不是像前面那样直接return啥也不返回了。因为返回0，下面的num要加上的\n",
    "        # 将 (i, j) 变成海水\n",
    "        grid[i][j] = 0\n",
    "\n",
    "        num = self.dfs(grid, i + 1, j) + self.dfs(grid, i, j + 1) + self.dfs(grid, i - 1, j) + self.dfs(grid, i, j - 1) + 1\n",
    "        # 最后那个+1，就是加上原来本身的那个岛屿。上下左右的岛屿+原来本身的岛屿\n",
    "\n",
    "        return num\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        self.area = 0\n",
    "        self.res = 0\n",
    "        m, n = len(grid), len(grid[0])\n",
    "            \n",
    "        # 遍历 grid\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    # 使用 DFS 将岛屿淹了并统计岛屿面积\n",
    "                    self.dfs(grid, i, j)\n",
    "                    if self.area>self.res:\n",
    "                        self.res = self.area\n",
    "                    self.area = 0\n",
    "        return self.res\n",
    "\n",
    "    # 从 (i, j) 开始，将与之相邻的陆地都变成海水\n",
    "    def dfs(self, grid: List[List[str]], i: int, j: int) -> None:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if i < 0 or j < 0 or i >= m or j >= n:\n",
    "            # 超出索引边界\n",
    "            return\n",
    "        if grid[i][j] == 0:\n",
    "            # 已经是海水了\n",
    "            return\n",
    "        # 将 (i, j) 变成海水\n",
    "        grid[i][j] = 0\n",
    "\n",
    "        # 封闭岛屿才统计面积\n",
    "        self.area += 1\n",
    "\n",
    "        # 淹没上下左右的陆地\n",
    "        self.dfs(grid, i + 1, j)\n",
    "        self.dfs(grid, i, j + 1)\n",
    "        self.dfs(grid, i - 1, j)\n",
    "        self.dfs(grid, i, j - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self,grid,cur_i,cur_j)->int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        if cur_i<0 or cur_j<0 or cur_i==m or cur_j==n or grid[cur_i][cur_j]!=1:\n",
    "            return 0\n",
    "        ans=1\n",
    "        grid[cur_i][cur_j]=0\n",
    "        for di,dj in [[0,1],[0,-1],[1,0],[-1,0]]:\n",
    "            next_i,next_j=cur_i+di,cur_j+dj\n",
    "            ans+=self.dfs(grid,next_i,next_j)\n",
    "        return ans\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        ans=0\n",
    "        for i,l in enumerate(grid):\n",
    "            for j,n in enumerate(l):\n",
    "                ans=max(ans,self.dfs(grid,i,j))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        def dfs(i, j) -> int:\n",
    "            grid[i][j] = 0  # 访问标记, 防止重复访问\n",
    "            res = 1\n",
    "            for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):\n",
    "                if 0 <= ni < m and 0 <= nj < n and grid[ni][nj]:\n",
    "                    res += dfs(ni, nj)\n",
    "            return res\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    ans = max(ans, dfs(i, j))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self,grid,cur_i,cur_j)->int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        if cur_i<0 or cur_j<0 or cur_i==m or cur_j==n or grid[cur_i][cur_j]!=1:\n",
    "            return 0\n",
    "        ans=1\n",
    "        grid[cur_i][cur_j]=0\n",
    "        for di,dj in [[0,1],[0,-1],[1,0],[-1,0]]:\n",
    "            next_i,next_j=cur_i+di,cur_j+dj\n",
    "            ans+=self.dfs(grid,next_i,next_j)\n",
    "        return ans\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        ans=0\n",
    "        for i,l in enumerate(grid):\n",
    "            for j,n in enumerate(l):\n",
    "                ans=max(ans,self.dfs(grid,i,j))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        rownum = len(grid)\n",
    "        colnum = len(grid[0])\n",
    "        seen = set()  # 使用集合而不是列表来存储已访问的坐标\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(x, y):\n",
    "            nonlocal temp\n",
    "            if 0 <= x < rownum and 0 <= y < colnum and grid[x][y] == 1 and (x, y) not in seen:\n",
    "                seen.add((x, y))\n",
    "                return 1 + dfs(x + 1, y) + dfs(x - 1, y) + dfs(x, y + 1) + dfs(x, y - 1)\n",
    "            return 0\n",
    "\n",
    "        for i in range(rownum):\n",
    "            for j in range(colnum):\n",
    "                if grid[i][j] == 1 and (i, j) not in seen:\n",
    "                    temp = 0\n",
    "                    area = dfs(i, j)\n",
    "                    ans = max(ans, area)\n",
    "\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self,curi,curj,m,n,grid) -> int:\n",
    "        if curi <0 or curi >m-1 or curj <0 or curj >n-1 or grid[curi][curj] != 1:\n",
    "            return 0\n",
    "        ret = 1\n",
    "        grid[curi][curj] = 0\n",
    "        for x,y in [[0,-1],[0,1],[-1,0],[1,0]]:\n",
    "            ret += self.dfs(curi+x,curj+y,m,n,grid)\n",
    "        return ret\n",
    "\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        row,col = len(grid),len(grid[0])\n",
    "        for i,rown in enumerate(grid):\n",
    "            for j,digit in enumerate(rown):\n",
    "                new = self.dfs(i,j,row,col,grid)\n",
    "                ans = max(ans,new)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        # dfs 如果是1的话 就遍历它的邻居\n",
    "        # 遍历过需要设置标志 避免重复访问\n",
    "\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        visited = set()\n",
    "        ans = 0\n",
    "        tmp = 0\n",
    "\n",
    "        def dfs(i,j):\n",
    "            nonlocal tmp\n",
    "            nonlocal ans\n",
    "            if i<0 or i==m or j<0 or j==n:\n",
    "                return\n",
    "            # 访问邻居 上下左右\n",
    "            for x,y in [[0,1],[0,-1],[1,0],[-1,0]]:\n",
    "                x += i\n",
    "                y += j\n",
    "                if 0<=x<m and 0<=y<n and (x,y) not in visited and grid[x][y]==1:\n",
    "                    visited.add((x,y))\n",
    "                    tmp += 1\n",
    "                    ans = max(ans,tmp)\n",
    "                    dfs(x,y)\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1 and (i,j) not in visited:\n",
    "                    visited.add((i,j))\n",
    "                    tmp = 1\n",
    "                    dfs(i,j)\n",
    "                    \n",
    "        return max(ans,tmp)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                ans = max(self.dfs(grid, i, j), ans)\n",
    "        return ans\n",
    "    \n",
    "    def dfs(self, grid, i, j):\n",
    "        if not 0 <= i < len(grid) or not 0 <= j < len(grid[0]) or grid[i][j] == 0:\n",
    "            return 0\n",
    "        area = 1\n",
    "        grid[i][j] = 0\n",
    "        for ni, nj in [[i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]]:\n",
    "            area += self.dfs(grid, ni, nj)\n",
    "        return area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def dfs(self, m, n, grid):\n",
    "\n",
    "        grid[m][n] = 0\n",
    "        res = 1\n",
    "        for x, y in [m+1, n], [m-1, n], [m, n-1], [m, n+1]:\n",
    "            if x > -1 and x < len(grid) and y > -1 and y < len(grid[0]):\n",
    "                if grid[x][y] == 1:\n",
    "                    res += self.dfs(x, y, grid)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        for i, _ in enumerate(grid):\n",
    "            for j, _ in enumerate(grid[0]):\n",
    "                if grid[i][j] == 1:\n",
    "                    res = max(res, self.dfs(i, j, grid))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        out = 0\n",
    "        for i, temp in enumerate(grid):\n",
    "            for j, n in enumerate(temp):\n",
    "                out = max(self.dfs(grid, i, j), out)\n",
    "        return out\n",
    "        \n",
    "\n",
    "    def dfs(self, grid, i, j) -> int:\n",
    "        if i < 0 or j < 0 or i == len(grid) or j == len(grid[0]) or grid[i][j] != 1:\n",
    "            return 0\n",
    "        grid[i][j] = 0 \n",
    "        out = 1\n",
    "        for di, dj in [[0,-1], [0, 1], [-1, 0], [1, 0]]:\n",
    "            next_i, next_j = i + di, j + dj\n",
    "            out += self.dfs(grid, next_i, next_j)\n",
    "        return out\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, grid, cur_i, cur_j) -> int:\n",
    "        if cur_i < 0 or cur_j < 0 or cur_i == len(grid) or cur_j == len(grid[0]) or grid[cur_i][cur_j] != 1:\n",
    "            return 0\n",
    "        grid[cur_i][cur_j] = 0\n",
    "        ans = 1\n",
    "        for di, dj in [[0, 1], [0, -1], [1, 0], [-1, 0]]:\n",
    "            next_i, next_j = cur_i + di, cur_j + dj\n",
    "            ans += self.dfs(grid, next_i, next_j)\n",
    "        return ans\n",
    "\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        for i, l in enumerate(grid):\n",
    "            for j, n in enumerate(l):   \n",
    "                ans = max(self.dfs(grid, i, j), ans)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        def getArea(x:int,y:int) -> int:\n",
    "            nonlocal grid\n",
    "            if x < 0 or y < 0 or x == len(grid) or y == len(grid[0]) or grid[x][y] !=1 :\n",
    "                return 0\n",
    "\n",
    "            grid[x][y] = 0\n",
    "            ret = 1\n",
    "            \n",
    "            for i,j in [[0,1],[1,0],[-1,0],[0,-1]]:\n",
    "                ret += getArea(x+i,y+j)\n",
    "            \n",
    "            return ret\n",
    "            \n",
    "        for i,l in enumerate(grid):\n",
    "            for j,num in enumerate(l):\n",
    "                    ans = max(ans,getArea(i,j))\n",
    "        \n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, m, n, matrix):\n",
    "        matrix[m][n] = 0\n",
    "        res = 1\n",
    "        for x, y in [m+1, n], [m-1, n], [m, n+1], [m, n-1]:\n",
    "            if x > -1 and x < len(matrix) and y > -1 and y < len(matrix[0]):\n",
    "                if matrix[x][y] == 1:\n",
    "                    res += self.dfs(x, y, matrix)\n",
    "        return res\n",
    "\n",
    "\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        for i, _ in enumerate(grid):\n",
    "            for j, _ in enumerate(grid[0]):\n",
    "                if grid[i][j] == 1:\n",
    "                    ans = max(ans, self.dfs(i, j, grid))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self,grid,cur_i,cur_j):\n",
    "        if cur_i < 0 or cur_j < 0 or cur_i == len(grid) or cur_j == len(grid[0]) or grid[cur_i][cur_j] != 1:\n",
    "            return 0\n",
    "        grid[cur_i][cur_j] = 0\n",
    "        ans = 1\n",
    "        for di,dj in [[0,1],[0,-1],[1,0],[-1,0]]:\n",
    "            next_i,next_j = cur_i+di,cur_j+dj\n",
    "            ans += self.dfs(grid,next_i,next_j)\n",
    "        return ans\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                ans = max(ans,self.dfs(grid,i,j))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, grid, cur_i, cur_j) -> int:\n",
    "        if cur_i < 0 or cur_j < 0 or cur_i == len(grid) or cur_j == len(grid[0]) or grid[cur_i][cur_j] != 1:\n",
    "            return 0\n",
    "        grid[cur_i][cur_j] = 0\n",
    "        ans = 1\n",
    "        for di, dj in [[0, 1], [0, -1], [1, 0], [-1, 0]]:\n",
    "            next_i, next_j = cur_i + di, cur_j + dj\n",
    "            ans += self.dfs(grid, next_i, next_j)\n",
    "        return ans\n",
    "\n",
    "    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        for i, l in enumerate(grid):\n",
    "            for j, n in enumerate(l):\n",
    "                ans = max(self.dfs(grid, i, j), ans)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
